作图网站都有哪些,企业网站怎么做推广,怎样制作网页新手自学入门,深圳专业网站建设平台文章目录1. 题目2. 解题1. 题目
在一个 N x N 的坐标方格 grid 中#xff0c;每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。
现在开始下雨了。当时间为 t 时#xff0c;此时雨水导致水池中任意位置的水位为 t 。 你可以从一个平台游向四周相邻的任意一个平台每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。
现在开始下雨了。当时间为 t 时此时雨水导致水池中任意位置的水位为 t 。 你可以从一个平台游向四周相邻的任意一个平台但是前提是此时水位必须同时淹没这两个平台。 假定你可以瞬间移动无限距离也就是默认在方格内部游动是不耗时的。 当然在你游泳的时候你必须待在坐标方格里面。
你从坐标方格的左上平台 (00) 出发。 最少耗时多久你才能到达坐标方格的右下平台 (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 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目LeetCode 1102. 得分最高的路径优先队列BFS/极大极小化 二分查找
跟上面题目一样这题是找到 路径最大值 最小的路径只需要在二分查找的地方做点修改
class Solution {vectorvectorint dir { {1,0},{0,1},{0,-1},{-1,0}};int N;
public:int swimInWater(vectorvectorint grid) {int l grid[0][0], r 2500, mid, ans;N grid.size();while(l r){mid (l r) / 2;vectorvectorbool vis(N, vectorbool(N,false));if(dfs(grid,0,0, mid, vis)){ //可以找到一条路径其上的值都 midans mid;r mid-1;}elsel mid1;}return ans;}bool dfs(vectorvectorint grid, int x, int y, int MAX, vectorvectorbool 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 {vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};
public:int swimInWater(vectorvectorint A) {int m A.size(), n A[0].size(), i, j, x, y, k, ans A[0][0];vectorvectorbool visited(m, vectorbool(n,false));visited[0][0] true;priority_queuepoint,vectorpoint,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(im-1 jn-1)return ans;for(k 0; k 4; k){x i dir[k][0];y j dir[k][1];if(x0 xm y0 yn !visited[x][y]){q.push(point(x, y, A[x][y]));visited[x][y] true;}}}return ans;}
};52 ms 8.5 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
