1631. Path With Minimum Effort

這就是著名的Dijikstra

每次挑距離最短的那條邊, 然後走訪他, 直到走到終點

到終點時的最長邊, 就是我們需要的了

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> q;
        q.push({0, 0, 0});
        vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int res = 0;
        int m = heights.size();
        int n = heights[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        
        while(!q.empty()){
            auto cur = q.top();
            q.pop();
            int dis = cur[0];
            int i = cur[1];
            int j = cur[2];
            visited[i][j] = true;
            res = max(res, dis);
            if(i == m - 1 && j == n - 1) return res;
            for(auto dir: dirs){
                int x = i + dir[0];
                int y = j + dir[1];
                if(x < 0 || x >= m || y < 0 || y >= n || visited[x][y]){
                    continue;
                }
                int diff = abs(heights[i][j] - heights[x][y]);
                q.push({diff, x, y});
            }
        }
        return -1;
    }
};