0778. Swim in Rising Water

# 778. Swim in Rising Water#

## 题目 #

On an N x N `grid`, each square `grid[i][j]` represents the elevation at that point `(i,j)`.

Now rain starts to fall. At time `t`, the depth of the water everywhere is `t`. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most `t`. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.

You start at the top left square `(0, 0)`. What is the least time until you can reach the bottom right square `(N-1, N-1)`?

Example 1:

``````Input: [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.

You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.
``````

Example 2:

``````Input: [[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]]
Output: 16
Explanation:
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

The final route is marked in bold.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.
``````

Note:

1. `2 <= N <= 50`.
2. grid[i][j] is a permutation of [0, …, N*N - 1].

## 题目大意 #

• 2 <= N <= 50.
• grid[i][j] 位于区间 [0, …, N*N - 1] 内。

## 解题思路 #

• 给出一个 grid[i][j] 方格，每个格子里面表示游泳池里面平台的高度。t 时刻，游泳池中的水的高度是 t。只有水的高度到达了平台的高度以后才能游过去。问从 (0,0) 开始，最短多长时间能到达 (N-1, N-1) 。
• 这一题有多种解法。第一种解题思路是利用 DFS + 二分。DFS 是用来遍历是否可达。利用时间(即当前水淹过的高度)来判断是否能到达终点 (N-1, N-1) 点。二分用来搜索最终结果的时间。为什么会考虑用二分加速呢？原因是：时间从 0 - max 依次递增。max 是游泳池最高的平台高度。当时间从 0 增加到 max 以后，肯定能到达终点 (N-1, N-1) 点，因为水比所有平台都要高了。想快速找到一个时间 t 能使得 (0,0) 点和 (N-1, N-1) 点之间连通，那么就想到用二分加速了。判断是否取中值的条件是 (0,0) 点和 (N-1, N-1) 点之间是否连通。
• 第二种解题思路是并查集。只要是 (0,0) 点和 (N-1, N-1) 点没有连通，即不能游到终点，那么就开始 `union()` 操作，由于起点是 (0,0)，所以向右边 `i + 1` 和向下边 `j + 1` 开始尝试。每尝试完一轮，时间会加 1 秒，即高度会加一。直到 (0,0) 点和 (N-1, N-1) 点刚好连通，那么这个时间点就是最终要求的。

## 代码 #

``````
package leetcode

import (
"github.com/halfrost/LeetCode-Go/template"
)

// 解法一 DFS + 二分
func swimInWater(grid [][]int) int {
row, col, flags, minWait, maxWait := len(grid), len(grid[0]), make([][]int, len(grid)), 0, 0
for i, row := range grid {
flags[i] = make([]int, len(row))
for j := 0; j < col; j++ {
flags[i][j] = -1
if row[j] > maxWait {
maxWait = row[j]
}
}
}
for minWait < maxWait {
midWait := (minWait + maxWait) / 2
if flags[row-1][col-1] == midWait {
maxWait = midWait
} else {
minWait = midWait + 1
}
}
return minWait
}

func addFlags(grid [][]int, flags [][]int, flag int, row int, col int) {
if row < 0 || col < 0 || row >= len(grid) || col >= len(grid[0]) {
return
}
if grid[row][col] > flag || flags[row][col] == flag {
return
}
flags[row][col] = flag
}

// 解法二 并查集(并不是此题的最优解)
func swimInWater1(grid [][]int) int {
n, uf, res := len(grid), template.UnionFind{}, 0
uf.Init(n * n)
for uf.Find(0) != uf.Find(n*n-1) {
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if grid[i][j] > res {
continue
}
if i < n-1 && grid[i+1][j] <= res {
uf.Union(i*n+j, i*n+j+n)
}
if j < n-1 && grid[i][j+1] <= res {
uf.Union(i*n+j, i*n+j+1)
}
}
}
res++
}
return res - 1
}

``````

Sep 6, 2020