# 1631. Path With Minimum Effort
###### tags: `Leetcode` `BFS` `Dijkstra` `Priority Queue`
Link: https://leetcode.com/problems/path-with-minimum-effort/
## 思路
dijkstra
## Code

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m, n = len(heights), len(heights[0])
        cost = [[inf for i in range(n)]for _ in range(m)]
        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        pq = []
        cost[0][0] = 0
        heappush(pq, [0, 0, 0]) # cost x y
        while pq:
            c, x, y = heapq.heappop(pq)
            if x==m-1 and y==n-1: return c
            for dir in dirs:
                nextX = x+dir[0]
                nextY = y+dir[1]
                if nextX>=0 and nextX<m and nextY>=0 and nextY<n:
                    nextDist = max(cost[x][y], abs(heights[nextX][nextY]-heights[x][y]))
                    if cost[nextX][nextY]>nextDist:
                        cost[nextX][nextY] = nextDist
                        heappush(pq, [cost[nextX][nextY], nextX, nextY])
        return 0

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int m=heights.length, n=heights[0].length;
        int[][] costs = new int[m][n];
        int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        for(int i=0; i<m; i++){
            Arrays.fill(costs[i], Integer.MAX_VALUE);
        }
        
        Queue<int[]> pq = new PriorityQueue<>((a,b)->(a[2]-b[2]));
        pq.add(new int[]{0,0,0});
        costs[0][0] = 0;
        while(!pq.isEmpty()){
            int[] curr = pq.poll();
            if(curr[0]==m-1 && curr[1]==n-1) return curr[2];
            for(int[] dir:dirs){
                int nextx = curr[0]+dir[0];
                int nexty = curr[1]+dir[1];
                if(nextx>=0 && nextx<m && nexty>=0 && nexty<n){
                    int newDist = Math.max(curr[2], Math.abs(heights[nextx][nexty]-heights[curr[0]][curr[1]]));
                    if(newDist<costs[nextx][nexty]){
                        costs[nextx][nexty] = newDist;
                        pq.add(new int[]{nextx, nexty, newDist});
                    }
                }
            }
        }
        return 0;
    }
}