1
#define pii pair<int, pair<int, int>>
2

3
class Solution {
4
 public:
5
  // Directions (top, right, bottom, left)
6
  const int d4x[4] = {-1, 0, 1, 0}, d4y[4] = {0, 1, 0, -1};
7

8
  int minimumEffortPath(vector<vector<int>> &h) {
9
    int n = h.size(), m = h[0].size();
10
    // min-heap
11
    priority_queue<pii, vector<pii>, greater<pii>> pq;
12
    // to store distances from (0,0)
13
    vector<vector<int>> dis(n, vector<int>(m, INT_MAX));
14
    dis[0][0] = 0;
15
    pq.push({0, {0, 0}});
16

17
    // Dijstra algorithm
18
    while (!pq.empty()) {
19
      pii curr = pq.top();
20
      pq.pop();
21
      int d = curr.first, r = curr.second.first, c = curr.second.second;
22
      // bottom right position
23
      if (r == n - 1 && c == m - 1) return d;
24
      for (int i = 0; i < 4; ++i) {
25
        int nx = r + d4x[i], ny = c + d4y[i];
26
        // check if new position is invalid
27
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
28
        // nd => new distance: which is max of distance till now(d) and curr
29
        // distance (difference between heights of current cells)
30
        int nd = max(d, abs(h[nx][ny] - h[r][c]));
31
        if (nd < dis[nx][ny]) {
32
          dis[nx][ny] = nd;
33
          pq.push({nd, {nx, ny}});
34
        }
35
      }
36
    }
37
    return 0;
38
    // please upvote
39
  }
40
};