# **Leetcode筆記(Path With Minimum Effort)**

:::info
:information_source: 題目 : Path With Minimum Effort, 類型 : graph, 等級 : medium
日期 : 2023/12/01
:::

### 嘗試

---
### **優化**
用binary search 去找目標最小值，用這個目標最小值去走dfs

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        n, m = len(heights), len(heights[0])
        dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)]

        def dfs(r, c, limitEffort):
            if r == n - 1 and c == m - 1:
                return True
            if r < 0 or c < 0 or r >= n or c >= m or (r, c) in visited:
                return False
            
            visited.add((r, c))
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < m: # check if inside the boundary
                    if abs(heights[nr][nc] - heights[r][c]) <= limitEffort:
                        if dfs(nr, nc, limitEffort):
                            return True

        l, r = 0, 10 ** 6
        while l <= r:
            mid = (l + r) // 2
            visited = set() # has to renew it every time
            if dfs(0, 0, mid):
                r = mid - 1
            else:
                l = mid + 1

        return l

we could use Dijkstra's Algorithm which is used to find the shortest path in a weighted graph with a slight modification of criteria for the shortest path.
永遠先pop調最小effort的，無論和當前走的path沒任何關係，這樣能確保到達終點時，effort是最小值

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        n, m = len(heights), len(heights[0])
        dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)]
        minHeap = [[0, 0, 0]] # [effort, r, c]
        visited = set()
        
        while minHeap:
            effort, r, c = heapq.heappop(minHeap)
            if r == n - 1 and c == m - 1:
                return effort

            visited.add((r, c))
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < m and (nr, nc) not in visited:
                    newEffort = max(effort, abs(heights[r][c] - heights[nr][nc]))
                    heapq.heappush(minHeap, [newEffort, nr, nc])

---

**思路**

**講解連結**
https://www.youtube.com/watch?v=XQlxCCx2vI4
Provided by. Neetcode