Krammer's blog

https://leetcode.com/problems/path-with-minimum-effort/ from Google

Thinking process:

This is a classic “finding path” problem. Usually, when we are asked about finding “minimum something” in a path, we use Dijkstra’s algorithm, so is this problem.

The below code is a classic template for BFS and Dijkstra. We basically use a tuple to store (minimum effort so far, row index, column index), and then put it into a priority queue. In c++, the priority queue is a max heap, so we need to negate the effort so that we can always pick the smallest route so far. We also need to make sure we don’t visit the same position unless the effort is less then before.

 1struct S
 2{
 3    int minEffort;
 4    int rowIndex;
 5    int colIndex;
 6
 7    S(int n1, int n2, int n3) : minEffort(n1), rowIndex(n2), colIndex(n3) {}
 8
 9    bool operator<(const struct S& other) const {
10        return minEffort < other.minEffort;
11    }
12};
13class Solution {
14public:
15    int minimumEffortPath(vector<vector<int>>& heights) {
16        int R = heights.size();
17        int C = heights[0].size();
18        vector<vector<int>> dp(R, vector<int>(C, INT_MAX));
19        priority_queue<S> q;
20        q.push(S(0,0,0));
21        vector<int> dirs{1,0,-1,0,1};
22        
23        auto getEffort = [&](int nr, int nc, int r, int c) {
24            return abs(heights[nr][nc]-heights[r][c]);
25        };
26        
27        auto isValidNextMove = [&](int nr, int nc, int r, int c, int h) {
28            return nr>=0 and nr<R and nc>=0 and nc<C 
29                and (max(h, getEffort(nr, nc, r, c)))<dp[nr][nc];
30        };
31        
32        while (q.size()) {
33            auto t = q.top(); q.pop();
34            int h = -t.minEffort, r = t.rowIndex, c = t.colIndex;
35            if (r == R-1 and c == C-1) return h;
36            for (int i=0; i<4; i++) {
37                int nr = r + dirs[i];
38                int nc = c + dirs[i+1];
39                if (isValidNextMove(nr, nc, r, c, h)) {
40                    int effort = getEffort(nr, nc, r, c);
41                    q.push(S(-max(h, effort), nr, nc));
42                    dp[nr][nc] = max(h, effort);
43                }
44            }
45        }
46        return -1;
47    }
48};

Editorial: LeetCode 1631 Path With Minimum Effort