水位上升的泳池中游泳

难度: Hard

在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。

当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间。

示例 1:

输入: grid = [[0,2],[1,3]]
输出: 3
解释:
时间为0时，你位于坐标方格的位置为 (0, 0)。
此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。
等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置

示例 2:

输入: grid = [[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
解释: 最终的路线用加粗进行了标记。
我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的

提示:

n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n²
grid[i][j] 中每个值 均无重复

Submission

运行时间: 32 ms

内存: 17.0 MB

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]

        def exist(val):
            vis = [[False] * n for _ in range(n)]

            def dfs(x, y):
                if x == y == n - 1:
                    return True

                vis[x][y] = True
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if not (0 <= nx < n and 0 <= ny < n) or vis[nx][ny]:
                        continue
                    if grid[nx][ny] <= val and dfs(nx, ny):
                        return True

                return False

            return dfs(0, 0)

        l, r = max(grid[0][0], grid[-1][-1]), n ** 2 - 1
        while l <= r:
            mid = (l + r) // 2
            if exist(mid):
                r = mid - 1
            else:
                l = mid + 1

        return l

Explain

这个题解采用了二分查找和深度优先搜索（DFS）相结合的方法。主要思路是：我们可以将最终到达的时间 t 视为一个区间，然后使用二分查找来找到最小的可行时间。对于每个时间 t，我们使用 DFS 来判断在时间 t 时是否可以从起点游到终点。如果可以到达，说明时间 t 可行，我们缩小右边界；否则时间 t 不可行，我们增大左边界。最终左边界就是最少需要的时间。

时间复杂度: O(n^2 * log(n))

空间复杂度: O(n^2)

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]

        def exist(val):
            vis = [[False] * n for _ in range(n)]  # 记录访问过的单元格

            def dfs(x, y):
                if x == y == n - 1:  # 到达终点
                    return True

                vis[x][y] = True  # 标记当前单元格已访问
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if not (0 <= nx < n and 0 <= ny < n) or vis[nx][ny]:  # 越界或已访问
                        continue
                    if grid[nx][ny] <= val and dfs(nx, ny):  # 相邻单元格可达且深度优先搜索可达终点
                        return True

                return False

            return dfs(0, 0)  # 从起点开始深度优先搜索

        l, r = max(grid[0][0], grid[-1][-1]), n ** 2 - 1  # 二分查找的左右边界
        while l <= r:
            mid = (l + r) // 2
            if exist(mid):  # 时间 mid 可行
                r = mid - 1
            else:  # 时间 mid 不可行
                l = mid + 1

        return l  # 返回最少需要的时间

Explore

在这个问题中，左边界代表我们可以开始尝试从起点游到终点的最小时间。因为我们一定至少需要等到起点和终点的水位高度低于或等于我们的时间点，所以左边界设置为起点 grid[0][0] 和终点 grid[-1][-1] 的最大值。如果从0开始，将包含很多不必要的值，因为在水位高于起点或终点的情况下，显然是无法开始游泳的。

在深度优先搜索中，当访问到某个单元格(x, y)时，意味着这个单元格的高度肯定是小于或等于当前的时间值 val 的，否则我们就不会访问它。因此在检查相邻单元格(nx, ny)时，只需要确认这个单元格的高度是否小于或等于 val。如果是，我们可以进一步探索这个单元格。这个比较确保了从当前单元格到相邻单元格的移动是可行的。

递归方式实现DFS相对直观和易于编码，特别是在处理像这样的二维网格问题时。递归方法自然地反映了问题的结构：每个单元格尝试访问它的邻居，如果成功，则继续向下探索。而迭代方法虽然可以避免深度递归可能导致的栈溢出问题，但编码复杂度通常更高，且在实现上不如递归直观。优点是递归简洁，易于理解；缺点是在极端情况下可能会造成栈溢出。迭代的优点是控制更加灵活，适合处理大规模数据；缺点是实现复杂度高。

为了避免在DFS搜索中重复访问单元格，我们使用一个访问矩阵 vis 来记录哪些单元格已被访问。在每次尝试访问新单元格之前，我们首先检查这个单元格是否已经在访问矩阵中标记为已访问。此外，我们还需要检查单元格是否越界。这样的处理确保了每个单元格仅被访问一次，有效防止了循环引用。