1631. Path With Minimum Effort (dijkstra

這題會一直帶著 effort from start to end

所以中間要更新時, 要最大的(origin effort and new effort)

但排出 pq 時, 要最小的, 這樣最後才會是 min effort

time: O(m*n * log(m*n))
space: O(m*n) // efftor matrix

use Dijkstra's algo

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        int effort[][] = new int[m][n];
        for (int i = 0; i < m ; i++) {
            Arrays.fill(effort[i], Integer.MAX_VALUE);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, 0, 0});
        
        while (!pq.isEmpty()) {
            int min[] = pq.poll();
            int dist = min[0];
            int row = min[1];
            int col = min[2];
            
            if (dist > effort[row][col]) { // prunig
                continue;
            }
            if (row == m - 1 && col == n - 1) {
                return dist;
            }
            
            int dir[][] = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
            
            for (int d[] : dir) {
                int newRow = row + d[0];
                int newCol = col + d[1];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
                    
                    // notie here
                    int newDist = Math.max(dist, Math.abs(heights[newRow][newCol] - heights[row][col]));
                    if (newDist < effort[newRow][newCol]) {
                        effort[newRow][newCol] = newDist;
                        pq.offer(new int[]{newDist, newRow, newCol});
                    }
                }
            }
        }
        return 0;
    }
}

use a class to hold pq's data

class Solution {
    private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    class State {
        int x;
        int y;
        int dist;
        State(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
    public int minimumEffortPath(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        
        Queue<State> pq = new PriorityQueue<>((a, b) -> a.dist - b.dist);
        pq.offer(new State(0, 0, 0));
        int[][] visited = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        
        while (!pq.isEmpty()) {
            State cur = pq.poll();
            int x = cur.x;
            int y = cur.y;
            int dist = cur.dist;
            if (dist > visited[x][y]) {
                continue;
            }
            if (x == m-1 && y == n-1) {
                return dist;
            }
            for (int[] dir : DIRS) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                if (!isValid(heights, newX, newY)) {
                    continue;
                }
                
                // max (dist, diff)
                int newDist = Math.max(dist, Math.abs(heights[x][y] - heights[newX][newY]));
                if (newDist < visited[newX][newY]) {
                    visited[newX][newY] = newDist;
                    pq.offer(new State(newX, newY, newDist));
                }
            }
        }
        return 0;
    }
    private boolean isValid(int[][] heights, int x, int y) {
        int m = heights.length;
        int n = heights[0].length;
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

/*
A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.

so effort is cell to cell's diff (maximum absolute difference)

cal the smallest effort

minimum effort required to travel from the top-left cell to the bottom-right cell.

so start: (0, 0)
   end  : (m-1, n-1)
   
effort: abs(cur x, y - next x, y)
pq: (x, y, effort)
update dist = min(dist, effor)

(0, 0, 0)

[x][y] = 1

(0, 1, 1) => choose this, dist = 1

if (newDist < effor[][]) {
   efforp[][] = newDist;
   
}

(1, 0, 2)
*/

new version

```java
class Solution {
    private static final int[][] DIRECTIONS = {{0,1}, {1, 0}, {0, -1}, {-1, 0}};
    class State {
        int x;
        int y;
        int effort;
        State(int x, int y, int effort) {
            this.x = x;
            this.y = y;
            this.effort = effort;
        }
    }
    public int minimumEffortPath(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;

        int[][] effortTo = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(effortTo[i], Integer.MAX_VALUE);
        }
        effortTo[0][0] = 0; // mark start effor = 0

        Queue<State> pq = new PriorityQueue<>((a, b) -> a.effort - b.effort);
        pq.offer(new State(0, 0, 0));

        while (!pq.isEmpty()) {
            State currState = pq.poll();
            if (currState.x == m-1 && currState.y == n-1) {
                return currState.effort;
            }

            for (int[] dir : DIRECTIONS) {
                int nextX = currState.x + dir[0];
                int nextY = currState.y + dir[1];
                if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n) {
                    int newEffort = Math.max(
                        currState.effort, 
                        Math.abs(heights[nextX][nextY] - heights[currState.x][currState.y])
                    );
                    if (effortTo[nextX][nextY] > newEffort) {
                        effortTo[nextX][nextY] = newEffort;
                        pq.offer(new State(nextX, nextY, newEffort));
                    }
                }
            }
        }
        return -1;
    }
}


/*
effort, if new curr to next effort < existing effort in nodes 
use Dikstra to maintain ""min effort in the path""
-> keep going, add to queue

A route's effort is the maximum ""absolute"" difference in heights between two consecutive cells of the route.
*/
```