免费网站系统下载,做接口的网站,婚庆公司简介范文,文章发表有稿费的平台778. 水位上升的泳池中游泳在一个 N x N 的坐标方格 grid 中#xff0c;每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。现在开始下雨了。当时间为 t 时#xff0c;此时雨水导致水池中任意位置的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台#xff0c…778. 水位上升的泳池中游泳在一个 N x N 的坐标方格 grid 中每一个方格的值 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解释:0 1 2 3 424 23 22 21 512 13 14 15 1611 17 18 19 2010 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;}}
