Swim in Rising Water

Q: Swim in Rising Water 的时间复杂度是多少？

使用 Dijkstra 算法时，时间复杂度为 O(n² log n)：n² 个单元格中的每个单元格在堆中最多入堆和出堆一次。对水位进行二分查找的复杂度相同，大约需要进行 log2(n²) 次洪泛搜索，每次复杂度为 O(n²)。两种方法都使用 O(n²) 的内存。

Q: 能用二分查找解决「水位上升」问题吗？

是的。你能否在第 t 级穿过网格，只会变化一次：在答案处从 false 变为 true。对 t 进行二分查找，并用泛洪填充作为测试，大约需要进行 log2(n²) 次填充；对于 100 × 100 的网格，需要 14 次。

Q: 并查集能解决“水位上升时游泳”问题吗？

是的。按高度顺序打开单元格，将每个新打开的单元格与相邻的已打开单元格合并，并在两个角落属于同一个集合时立即停止。你最后打开的单元格的高度就是答案。由于从 0 到 n²-1 的每个值都只出现一次，因此可以用一个从高度映射到单元格的表来确定顺序，无需排序。

困难最短路径堆二分查找

+10

你会得到一个 n × n 的高度网格，其中包含从 0 到 n²-1 的每个数字，且每个数字恰好出现一次。在时间 t，各处的水位都达到高度 t，因此高度为 t 或更低的所有格子都被水淹没。你从左上角的格子出发。当你所在的格子和与它共边的格子都被水淹没时，你可以在不耗费时间的情况下游到那个格子。返回你最早能到达右下角格子的时间。

函数

swimInWater(grid: integer-2d-array) → integer

gridinteger-2d-array: 高度，表示为由 n 行组成的列表，每行有 n 个数字
返回值integer: 你能到达右下角单元格的最早时间

约束条件

n == grid.length == grid[i].length
1 ≤ n ≤ 100
0 ≤ grid[i][j] ≤ n²-1
从 0 到 n²-1 的每个值都恰好出现一次。

示例

输入: grid = [[0, 2], [3, 1]]
输出: 2
解释: 经过右上方单元格的路线是 0、2、1，其中最高的单元格是 2。经过左下方单元格的路线是 0、3、1，其中最高的单元格是 3。在时间 2 时，第一条路线已被水淹没。

进阶

如果高度可能重复，且达到 10^9，你的哪些方法仍然可以原样使用？你会对什么进行二分查找？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

一条路线所需的时间取决于其中海拔最高的格子，因为水必须淹没你经过的每个格子。因此，要找出连接两个角且最高格子海拔最低的路线：也就是代价取决于最高值而不是总和的最短路径。你可以逐步升高水位、对水位进行二分查找，或根据这种代价运行 Dijkstra 算法。

一步一步地抬高水位

结果正确，但无法在最大的测试中运行完毕

思路

固定一个水位 t。从左上角开始进行一次泛洪填充，只经过高度不超过 t 的单元格，就能判断右下角是否可达。将 t 设为两个角中较高的高度，即 max(grid[0][0], grid[n-1][n-1])，因为两个角都必须被水淹没，然后每次加 1，直到填充能够到达终点。水位上升只会开放更多单元格，因此第一个可行的水位就是答案。

每次填充的开销是 O(n²)，而水位可能上升近 n² 次：在 100 × 100 的网格中，最多需要检查 10^4 个水位 × 10^4 个单元格，也就是约 10^8 次单元格访问。

算法

将 t 设为两个角落高度中较高的值。
从左上角开始，对高度不超过 t 的单元格进行洪泛填充，使用显式栈，并为每个单元格标记是否已访问。
如果填充到达右下角，则返回 t。
否则，将 t 加 1，然后再次填充。

def canReach(grid, t):
    # True when you can swim from the top left to the bottom right with the water at height t.
    n = len(grid)
    seen = [[False] * n for _ in range(n)]
    seen[0][0] = True
    stack = [(0, 0)]
    while stack:
        r, c = stack.pop()
        if r == n - 1 and c == n - 1:
            return True
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
                seen[nr][nc] = True
                stack.append((nr, nc))
    return False


def swimInWater(grid):
    n = len(grid)
    # You cannot finish before the water covers both corners.
    t = max(grid[0][0], grid[n - 1][n - 1])
    # Raise the water one step at a time until a way through opens.
    while not canReach(grid, t):
        t += 1
    return t

水位二分查找

思路

对于低于答案的每个水位，洪水填充测试都会失败；从答案对应的水位开始，测试都会成功。二分查找会找到这个临界水位，它位于较高的角点和 n²-1 之间，此时整个网格都被水淹没。

在 5 × 5 的示例中，lo = 6，hi = 24。水位 15 时测试失败，因此 lo = 16。水位 20、18、17 和 16 时测试都成功，搜索在进行 5 次填充后以 16 结束。

100 × 100 的网格有 10^4 个水位，因此大约 14 次填充就能确定结果：约需访问 1.4 × 10^5 个单元格，而不是 10^8 个。

算法

将 lo 设为较高的角落高度，将 hi 设为 n²-1。
当 lo < hi 时，取 mid = (lo + hi) / 2，向下取整。
在高度 mid 处进行泛洪填充。如果能到达右下角，就将 hi = mid；否则将 lo = mid + 1。
返回 lo。

def canReach(grid, t):
    # True when you can swim from the top left to the bottom right with the water at height t.
    n = len(grid)
    seen = [[False] * n for _ in range(n)]
    seen[0][0] = True
    stack = [(0, 0)]
    while stack:
        r, c = stack.pop()
        if r == n - 1 and c == n - 1:
            return True
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
                seen[nr][nc] = True
                stack.append((nr, nc))
    return False


def swimInWater(grid):
    n = len(grid)
    # The answer lies between the higher corner and the highest cell.
    lo = max(grid[0][0], grid[n - 1][n - 1])
    hi = n * n - 1
    # canReach is false below the answer and true from it on: find the first true.
    while lo < hi:
        mid = (lo + hi) // 2
        if canReach(grid, mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

在路线的最高单元格上运行 Dijkstra

思路

给每条路线设定一个代价：路线中最高的格子的高度。Dijkstra 算法仍然适用，因为将路线延伸到高度为 h 的格子时，代价为 max(old cost, h)，绝不会低于原来的代价。使用一个以时间为键的最小堆来存储格子，从左上角的 grid[0][0] 开始。当右下角离开堆时，它对应的时间就是答案。

你可以在第一次将格子推入堆时就把它标记为已访问。格子按时间顺序离开堆，因此第一个到达某个邻居的格子，能为它提供所有格子中可能的最小时间，并且每个格子只会进入堆一次。

堆中保存着你能够到达的区域边缘，每次弹出格子时，水位都会恰好升高到足以让你走到那里。在这个 5 × 5 的示例中，弹出的时间依次为 0、1、2、3、4、5，然后到达时间为 16 的关卡，最后右下角以 16 离开堆。

算法

将左上角标记为已访问，并将其与时间 grid[0][0] 一起推入。
弹出时间 t 最小的单元格。如果它是右下角，则返回 t。
对于每个尚未访问的邻居，将其标记为已访问，并以时间 max(t, its height) 将其推入。
从第 2 步开始重复。

import heapq


def swimInWater(grid):
    n = len(grid)
    seen = [[False] * n for _ in range(n)]
    seen[0][0] = True
    # (time, row, col): the time is the highest cell on the best path found to that cell.
    heap = [(grid[0][0], 0, 0)]
    while True:
        t, r, c = heapq.heappop(heap)
        # Cells leave the heap in order of time, so this is the earliest you can be here.
        if r == n - 1 and c == n - 1:
            return t
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc]:
                # Reached for the first time from the cell with the smallest time:
                # no later route can arrive earlier, so mark it now.
                seen[nr][nc] = True
                heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))

易错点和边界情况

忽略角落自身的高度。答案至少是 grid[0][0] 和 grid[n-1][n-1] 中的较大值：对于 [[3, 0], [1, 2]]，答案是 3。
贪心地走向最低的邻居。最佳路线可能需要爬到一道关卡，然后绕远路过去，就像 5 × 5 的示例那样。
像普通最短路径那样累加路线上的高度。新的时间是 max(t, height)，而不是 t + height。
使用递归进行洪泛填充。蜿蜒的路线可能长达数千个单元格，这会超出 Python 的 1,000 层嵌套调用限制。

常见问题3

Swim in Rising Water 的时间复杂度是多少？

使用 Dijkstra 算法时，时间复杂度为 O(n² log n)：n² 个单元格中的每个单元格在堆中最多入堆和出堆一次。对水位进行二分查找的复杂度相同，大约需要进行 log2(n²) 次洪泛搜索，每次复杂度为 O(n²)。两种方法都使用 O(n²) 的内存。

能用二分查找解决「水位上升」问题吗？

是的。你能否在第 t 级穿过网格，只会变化一次：在答案处从 false 变为 true。对 t 进行二分查找，并用泛洪填充作为测试，大约需要进行 log2(n²) 次填充；对于 100 × 100 的网格，需要 14 次。

并查集能解决“水位上升时游泳”问题吗？

是的。按高度顺序打开单元格，将每个新打开的单元格与相邻的已打开单元格合并，并在两个角落属于同一个集合时立即停止。你最后打开的单元格的高度就是答案。由于从 0 到 n²-1 的每个值都只出现一次，因此可以用一个从高度映射到单元格的表来确定顺序，无需排序。

def swimInWater(grid):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

grid = [[0, 2], [3, 1]]

预期输出