# 1631. Path With Minimum Effort (dijkstra

![](/files/-Mdgk7FEmV5TuDgjCFb_)

![](/files/-MdgkAuK5bJaSzDVW5hR)

![](/files/-MdgkEBVoYiwFva7HvAe)

![](/files/-MdgkJNi9SgjL6kcmIK7)

這題會一直帶著 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
```

```java
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

```java
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
```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.
*/
```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/1631.-path-with-minimum-effort.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.