1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

typedef std::pair<int, std::pair<int, int>> PIPII;

class Solution {
public:
    int minimumEffortPath(std::vector<std::vector<int>>& heights) {
        int m = heights.size();
        int n = heights[0].size();
        std::vector<std::vector<int>> visited(m, std::vector<int>(n, 0));
        std::vector<std::vector<int>> dist(m, std::vector<int>(n, 0x3fff'ffff));
        
        int dirs[4][2] = { {0, 1}, {1, 0}, {-1, 0}, {0, -1} };
        std::priority_queue<PIPII, std::vector<PIPII>, std::greater<PIPII>> pq;
        pq.push({0, {0, 0}});
        
        while (!pq.empty()) {
            int d = pq.top().first;
            int x = pq.top().second.first;
            int y = pq.top().second.second;
            pq.pop();
            if (d > dist[x][y]) {
                continue;
            }
            if (x == m - 1 && y == n - 1) {
                return d;
            }
            
            for (auto& dir : dirs) {
                int xx = x + dir[0];
                int yy = y + dir[1];
                if (xx >= 0 && xx < m && yy >= 0 && yy < n && !visited[xx][yy]) {
                    int nd = std::max(d, std::abs(heights[xx][yy] - heights[x][y]));
                    if (nd < dist[xx][yy]) {
                        dist[xx][yy] = nd;
                        pq.push({nd, {xx, yy}});
                    }
                }
            }
        }
        
        return -1;
    }
};