在一个 N x N 的坐标方格 grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。
现在开始下雨了。当时间为 t 时，此时雨水导致水池中任意位置的水位为 t 。 你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。 假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。 当然，在你游泳的时候你必须待在坐标方格里面。
你从坐标方格的左上平台 (0，0) 出发。 最少耗时多久你才能到达坐标方格的右下平台 (N-1, N-1)？
示例 1: 输入: [[0,2],[1,3]] 输出: 3 解释: 时间为0时，你位于坐标方格的位置为 (0, 0)。 此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。 等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的， 所以你可以游向坐标方格中的任意位置 示例2: 输入: [[0,1,2,3,4], [24,23,22,21,5], [12,13,14,15,16], [11,17,18,19,20], [10,9,8,7,6]] 输出: 16 最终的路线用加粗进行了标记。 我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的 提示: 2 <= N <= 50. grid[i][j] 位于区间 [0, ..., N*N - 1] 内。来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/swim-in-rising-water 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
类似题目：LeetCode 1102. 得分最高的路径（优先队列BFS/极大极小化 二分查找）
跟上面题目一样，这题是找到 路径最大值 最小的路径，只需要在二分查找的地方做点修改
class Solution { vector<vector<int>> dir = { {1,0},{0,1},{0,-1},{-1,0}}; int N; public: int swimInWater(vector<vector<int>>& grid) { int l = grid[0][0], r = 2500, mid, ans; N = grid.size(); while(l <= r) { mid = (l + r) / 2; vector<vector<bool>> vis(N, vector<bool>(N,false)); if(dfs(grid,0,0, mid, vis)) { //可以找到一条路径，其上的值都 <= mid ans = mid; r = mid-1; } else l = mid+1; } return ans; } bool dfs(vector<vector<int>>& grid, int x, int y, int MAX, vector<vector<bool>>& vis) { vis[x][y] = true; int i, j, k; if(x == N-1 && y == N-1) { return true; } for(k = 0; k < 4; k++) { i = x + dir[k][0]; j = y + dir[k][1]; if(i >=0 && i < N && j >=0 && j < N && !vis[i][j] && grid[i][j] <= MAX) { if(dfs(grid, i, j, MAX, vis)) return true; } } return false; } };36 ms 9.7 MB
优先队列也可以
struct point { int x; int y; int val; point(int x0, int y0, int v) { x = x0; y = y0; val = v; } }; struct cmp { bool operator()(point& a, point& b) { return a.val > b.val;//值小的优先 } }; class Solution { vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}}; public: int swimInWater(vector<vector<int>>& A) { int m = A.size(), n = A[0].size(), i, j, x, y, k, ans = A[0][0]; vector<vector<bool>> visited(m, vector<bool>(n,false)); visited[0][0] = true; priority_queue<point,vector<point>,cmp> q; q.push(point(0, 0, A[0][0])); while(!q.empty()) { if(q.top().val > ans) ans = q.top().val; i = q.top().x; j = q.top().y; q.pop(); if(i==m-1 && j==n-1) return ans; for(k = 0; k < 4; ++k) { x = i + dir[k][0]; y = j + dir[k][1]; if(x>=0 && x<m && y>=0 && y<n && !visited[x][y]) { q.push(point(x, y, A[x][y])); visited[x][y] = true; } } } return ans; } };52 ms 8.5 MB
我的博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
