leetcode 困难题 778. Swim in Rising Water 水位上升的泳池中游泳

Problem: 778. Swim in Rising Water 水位上升的泳池中游泳

解题过程

深度优先搜索，+ 记忆化搜索，找到每条路径的最大值，然后拿到所有路径最大值当中的最小值，记忆化搜索的key是(tmpMX << 20) + (x << 10) + y;，若当前路径最大值已经大于结果则if(tmpMX > mi) return mi;

Code

class Solution { public: int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; int mi = INT_MAX, n; vector<vector<bool>> status; unordered_map<int, int> ump; int dfs(vector<vector<int>>& grid, int x, int y, int tmpMX) { if(tmpMX > mi) return mi; if(x==n-1 && y==n-1) { mi = min(tmpMX, mi); return mi; } int key = (tmpMX << 20) + (x << 10) + y; if(ump.find(key)!=ump.end()) return ump[key]; int xx, yy, rtmi = INT_MAX, rt; if(status[x][y]) return mi; status[x][y] = true; for(int i = 0; i < 4; i++) { xx = x + dir[i][0]; yy = y + dir[i][1]; if(xx < 0 ||yy < 0 || xx >= n || yy >= n) { continue; } rt = dfs(grid, xx, yy, max(tmpMX, grid[xx][yy])); rtmi = min(rt, rtmi); } status[x][y] = false; ump[key] = rtmi; return rtmi; } int swimInWater(vector<vector<int>>& grid) { n = grid.size(); status.assign(n, vector<bool>(n, false)); dfs(grid, 0, 0, grid[0][0]); return mi; } };