Untitled
unknown
plain_text
2 years ago
1.2 kB
3
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; } };