Java实现 LeetCode 778 水位上升的泳池中游泳(二分+DFS)
2024-09-07 15:07:42
778. 水位上升的泳池中游泳
在一个 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
解释:
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,此时才能保证平台 (0, 0) 和 (4, 4) 是连通的
提示:
2 <= N <= 50.
grid[i][j] 位于区间 [0, …, N*N - 1] 内。
class Solution {
public int swimInWater(int[][] grid) {
int N = grid.length;
int lo = Math.max(grid[0][0], grid[N - 1][N -1]);
int hi = N * N - 1;
BitSet bs = new BitSet(hi);
while (lo < hi) {
int mi = (lo + hi) >> 1;
if (dfs(grid, 0, 0, mi, bs)) hi = mi;
else lo = mi + 1;
bs.clear();
}
return lo;
}
public boolean dfs (int[][] grid, int i, int j, int limit, BitSet bs) {
if (bs.get(i * grid.length + j) || grid[i][j] > limit) return false;
if (i == grid.length - 1 && j == grid.length - 1) return true;
bs.set(i * grid.length + j);
if (i < grid.length - 1 && dfs(grid, i + 1, j, limit, bs)) return true;
if (j < grid.length - 1 && dfs(grid, i, j + 1, limit, bs)) return true;
if (i > 0 && dfs(grid, i - 1, j, limit, bs)) return true;
if (j > 0 && dfs(grid, i, j - 1, limit, bs)) return true;
return false;
}
}
最新文章
- pandas中将timestamp转为datetime
- JavaScript学习笔记-实现枚举类型,扑克牌应用
- 湖大 11404 manacher
- 为什么用服务不用线程-Android
- js学习之函数表达式及闭包
- Axiom3D学习日记 1.程序配置
- 基于visual Studio2013解决C语言竞赛题之0419误差控制
- 学生表sid,sname,结果表cid,cname,学生成绩表sid,cid,cscore,最高要求的分数输出候补课程专门命名
- 实际情况来看,还是yield很爽
- 0423上课练习(list、while、def)
- 老男孩Python全栈学习 S9 日常作业 010
- 编程菜鸟的日记-初学尝试编程-C++ Primer Plus 第5章编程练习4
- 十个有意思的Github Page
- 【管用】 使用VMtools实现主机Windows与虚拟机Linux文件共享
- C# 值类型
- UOJ275 组合数问题
- less教程
- 以源码编译的方式安装PHP与php-fpm
- 使用Git代替FTP进行虚拟主机的代码管理
- matplotlib之极坐标系的极角网格线(thetagrids)的显示刻度