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:

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

题目大意

在一个 N x N 的坐标方格 grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。现在开始下雨了。当时间为 t 时，此时雨水导致水池中任意位置的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台 (N-1, 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
		addFlags(grid, flags, midWait, 0, 0)
		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
	addFlags(grid, flags, flag, row-1, col)
	addFlags(grid, flags, flag, row+1, col)
	addFlags(grid, flags, flag, row, col-1)
	addFlags(grid, flags, flag, row, col+1)
}

// 解法二 并查集(并不是此题的最优解)
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
}