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;

}

}

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的java圆形泳池问题_Java实现 LeetCode 778 水位上升的泳池中游泳（二分+DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。