# 1631. Path With Minimum Effort

###### tags: `leetcode`,`dp`,`medium`

>ref: https://leetcode.com/problems/path-with-minimum-effort/
>

>Example 1:
Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.

>Example 2:
Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].

>Constraints:
rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10^6

>1.timeResolution:O(NMlog NM)故需要對半拆 Space: O(M\*N)
>2. 建dist[][]紀錄每idx到達時的最低effort, 除dist[0][0]=0外其他設置為int.max_value
>3. 新座標過邊界條件後,當dist[r][c]更新為更低值時放入priorityQueue, 每次poll都會先取用最低dist進行評估,如此到達dist[r-1][c-1]才會是最低值

    public int minimumEffortPath(int[][] heights) {
        
        int[][] dir= new int[][]{{0,-1},{0,1},{-1,0},{1,0}};
        
        int row=heights.length;
        int col=heights[0].length;
        
        int[][] dist=new int[row][col];
        for(int[] a:dist){
            Arrays.fill(a,Integer.MAX_VALUE);
        }
        dist[0][0]=0;
        PriorityQueue<int[]> q= new PriorityQueue<>((arr1,arr2)->arr1[0]-arr2[0]);
        
        q.offer(new int[]{0,0,0});
        
        while(!q.isEmpty()){
            int[] cur= q.poll();
            
            int d=cur[0];
            int r=cur[1];
            int c=cur[2];
            
            if(d>dist[r][c])continue;
            if(r==row-1 && c==col-1) return d;
            
            for(int i=0;i<4;i++){
                int new_r=r+dir[i][0];
                int new_c=c+dir[i][1];
                if( (new_r>=0) && (new_r<row) && (new_c>=0) && (new_c<col) ){
                    int new_d=Math.max(d,Math.abs(heights[new_r][new_c]-heights[r][c]));
                    
                    if(new_d<dist[new_r][new_c]){
                        dist[new_r][new_c]=new_d;
                        q.offer(new int[]{dist[new_r][new_c],new_r,new_c});
                    }
                }
            }
            
        }
        
        return 0;
        
    }