Uber 最短桥：最少翻水格并输出路径

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入为 0/1 矩形网格，恰有两座按四方向相连的岛；1 是陆地，0 是水。
• 输出最少需要翻为陆地的水格坐标列表，按从第一座岛走向第二座岛的顺序；如果有多条最短桥，返回任意一条。
• 题目只说‘打印路径’，未明确是否要含两端陆地；本文训练接口只返回需翻转的水格，若需完整格路径可在两端补陆地坐标。

解题路线

1. 找任意陆地格，用 DFS/BFS 标记整座第一岛，将岛上所有格一起放入多源 BFS 队列，距离为 0。
2. 从第一岛向水域逐层扩展；首次访问一个水格时只存 previous[水格]=前一格，不复制整条路径。第一次碰到另一座岛时即达到最少翻格数。
3. 从接触第二岛前的水格沿 previous 回溯，直到回到第一岛，反转得到水格路径。多源 BFS 的层次保证路径最短。

手动走一遍

网格 [[1,0,1]] 有两座岛，翻 (0,1) 即形成最短桥，代码返回长度为 1 的水格列表。若保存每条队列路径，多个前缀会重复占内存。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Return water cells to flip for a shortest bridge between two islands."""

from collections import deque


def shortest_bridge_path(grid: list[list[int]]) -> list[tuple[int, int]]:
    if not grid or not grid[0] or any(len(row) != len(grid[0]) for row in grid):
        raise ValueError("nonempty rectangular grid required")
    if any(cell not in (0, 1) for row in grid for cell in row):
        raise ValueError("grid must contain 0/1")
    rows, cols = len(grid), len(grid[0])

    def neighbors(row, col):
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = row + dr, col + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                yield nr, nc

    start = next(((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == 1), None)
    if start is None:
        raise ValueError("no island")
    first = {start}
    island_queue = deque([start])
    while island_queue:
        cell = island_queue.popleft()
        for neighbor in neighbors(*cell):
            if grid[neighbor[0]][neighbor[1]] == 1 and neighbor not in first:
                first.add(neighbor)
                island_queue.append(neighbor)

    queue = deque(first)
    seen = set(first)
    previous: dict[tuple[int, int], tuple[int, int]] = {}
    while queue:
        cell = queue.popleft()
        for neighbor in neighbors(*cell):
            if neighbor in seen:
                continue
            if grid[neighbor[0]][neighbor[1]] == 1:
                path = []
                while cell not in first:
                    path.append(cell)
                    cell = previous[cell]
                return path[::-1]
            seen.add(neighbor)
            previous[neighbor] = cell
            queue.append(neighbor)
    raise ValueError("second island not found")

复杂度

第一岛遍历与多源 BFS 每格最多访问一次，时间 O(RC)；visited、队列与前驱表最坏 O(RC) 空间。回溯路径长度 L≤RC，输出 O(L)；队列存整条路径的做法可能产生远多于 O(RC) 的复制字符/坐标。

易错点与追问

容易失分的边界

• 只从第一岛某一个格开始 BFS 会把岛内距离算进去，可能错过从岛上其他边界出发的更短桥；应把整岛作为距离 0 源。
• 先把第二岛的陆地加入水格前驱并计成本会多翻一格；进入第二岛时即可停止。
• 题目要返回路径，只返回最少翻格数不完整；用 predecessor map 是对其空间追问的直接回应。

继续深挖

• 若有多于两座岛并要求任意两岛最短桥，可给每岛编号后做多源 BFS 并检测不同岛扩展波前相遇；需防止同一层重复计数。
• 若水格翻转成本不同，普通 BFS 失效，可在格图上使用 0-1 BFS 或 Dijkstra 并保留前驱。