Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.2 kB
2
Indexable
Never
class Solution {
public:
    map<pair<int,int>,bool> visited;
    map<pair<int,int>,map<pair<int,int>,int>> g;
    int n,m,ans = INT_MAX;
    void dfs(pair<int,int> src,int temp) {
        if(src == make_pair(n-1,m-1)){
            ans = min(ans,temp); return;
        }
        visited[src] = true;
        for(auto next : g[src]) {
            if(!visited[next.first]) {
                temp = max(temp,next.second);
                dfs(next.first,temp);
            }
        }
    }
    int minimumEffortPath(vector<vector<int>>& heights) {
        n = heights.size();
        m = heights[0].size();
        int dx[] = {0,0,1,-1};
        int dy[] = {1,-1,0,0};
        auto inside = [](int &a,int &b,int &n,int &m) { return (a < n && a >= 0 && b < m && b >= 0); };
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                for(int k = 0; k < 4; ++k){
                    int x = i + dx[k], y = j  + dy[k];
                    if(inside(x,y,n,m)){
                        g[{i,j}][{x,y}] = abs(heights[i][j] - heights[x][y]);
                    }
                }
            }
        }
        dbg(g);
        dfs({0,0},INT_MIN);
        return ans;
    }
};