# 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].

## # 解题方法

### # 并查集

• 昨天的题目是把相邻的两个格子之间的高度差的绝对值当作了边的权重，对边排序，逐渐添加边，看添加到哪个边的时候，起点和终点能连通；
• 今天的题目中，由于不用求高度差，而是求路径上的格子高度的最大值，因此，可以把抽象成为一个边的权重为 0 的无向图，然后对顶点排序，逐个添加上每个顶点，看添加到哪个点的时候，起点和终点能连通。

1. 先去除图中的所有顶点，然后按照顶点数值的从小到大的顺序，依次遍历并添加每个顶点；
2. 在每次遍历的过程中都要比较这个顶点的数值和其周围的 4 个相邻顶点的数值大小，来判断是否需要添加一条边：如果相邻节点的数值更小，说明该相邻顶点之前已经添加到图中，因此现在需要建立一条让两个顶点连通的边；如果相邻节点的数值更大，说明该相邻顶点之前没有添加到图中，因此不要建立连通的边。
3. 当添加某一个顶点之后，最左上角的顶点和最右下角的顶点连通了，说明该顶点就是所求。

![](https://img-blog.csdnimg.cn/img_convert/3db801dd20cb99441f5c6e3592c8b4d5.gif#align=left&display=inline&height=608&margin=[object Object]&name=&originHeight=608&originWidth=1080&size=0&status=done&style=none&width=1080)

### # 二分查找 + DFS

``````class Solution(object):
def swimInWater(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
n = len(grid)
left, right = 0, n * n - 1
while left <= right:
mid = left + (right - left) / 2
if self.dfs([[False] * n for _ in range(n)], grid, mid, n, 0, 0):
right = mid - 1
else:
left = mid + 1
return left

def dfs(self, visited, grid, mid, n, i, j):
visited[i][j] = True
if i == n - 1 and j == n - 1:
return True
directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
for dir in directions:
x, y = i + dir[0], j + dir[1]
if x < 0 or x >= n or y < 0 or y >= n or visited[x][y] or max(mid, grid[i][j]) != max(mid, grid[x][y]):
continue
if self.dfs(visited, grid, mid, n, x, y):
return True
return False
``````

### # 优先级队列改进的 BFS

``````class Solution(object):
def swimInWater(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
n = len(grid)
visited, pq = set((0, 0)), [(grid[0][0], 0, 0)]
res = 0
while pq:
T, i, j = heapq.heappop(pq)
res = max(res, T)
directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
if i == j == n - 1:
break
for dir in directions:
x, y = i + dir[0], j + dir[1]
if x < 0 or x >= n or y < 0 or y >= n or (x, y) in visited:
continue
heapq.heappush(pq, (grid[x][y], x, y))