LeetCode 934. 最短的桥

题目描述

给定一个二维二进制矩阵 grid，其中 1 表示陆地，0 表示水域。整个网格恰好包含两个岛屿（即连通的 1 的区域）。你可以将任意数量的 0 翻转为 1，以使两个岛屿连通，变成一个岛屿。你需要返回必须翻转的 0 的最小数目。

示例 1：
输入：grid = [[0,1],[1,0]]
输出：1

示例 2：
输入：grid = [[0,1,0],[0,0,0],[0,0,1]]
输出：2

示例 3：
输入：grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出：1

约束条件：

• n == grid.length == grid[i].length
• 2 <= n <= 100
• grid[i][j] 为 0 或 1
• 整个网格中恰好有两个岛屿

解题过程循序渐进讲解

这是一个典型的图论/搜索问题。核心思路是先找到并标记出两个不同的岛屿，然后从其中一个岛屿出发，通过广度优先搜索（BFS）寻找到达另一个岛屿的最短路径，路径长度即为需要翻转的 0 的数量。

第 1 步：理解问题核心

• 两个岛屿是独立的连通分量（由 1 组成）。
• 我们需要在它们之间建立一条最短的“桥”（由翻转 0 得到），桥的长度等于桥经过的 0 的格子数。
• 因为只能翻转 0，所以桥的起点必须是岛屿边缘的 1，终点是另一个岛屿边缘的 1，中间经过的都是 0。
• 问题转化为：从岛屿 A 的所有单元格出发，进行 BFS，第一次碰到岛屿 B 的任何一个单元格时，所经过的 0 的层数（距离）就是最小翻转数。

第 2 步：找到并标记第一个岛屿

我们可以使用深度优先搜索（DFS）或 BFS 来找到第一个岛屿的所有单元格，并对其进行标记（例如，将所有 1 改为 2）。同时，在遍历第一个岛屿时，我们记录下这个岛屿的所有边界水域格子（即与这些 1 相邻的 0 格子），这些将是后续 BFS 的起点集合。

为什么先找第一个岛屿？
因为我们需要区分两个岛屿，以便在 BFS 扩展时知道何时碰到了第二个岛屿。标记第一个岛屿后，未访问的 1 就属于第二个岛屿。

第 3 步：从第一个岛屿边界进行多源 BFS

我们将第 2 步中收集到的所有边界水域格子（0）加入 BFS 队列，并标记它们已访问（可以单独用一个 visited 数组，也可以在原数组上标记，比如改成 -1 表示已访问的 0）。

• BFS 的每一层，都从当前队列中的所有格子出发，向四个方向（上、下、左、右）扩展。
• 如果扩展到的格子是 0 且未访问，则将其标记为已访问，并加入队列，距离（层数）增加。
• 如果扩展到的格子是 1 且未被标记为第一个岛屿（即值仍为 1），说明我们碰到了第二个岛屿。此时，当前的 BFS 层数就是最短桥的长度（因为 BFS 保证首次遇到目标时的路径最短）。

第 4 步：具体步骤分解

假设网格为 grid，大小为 n x n。

步骤 4.1：初始化

• 找到一个 1 作为第一个岛屿的起点（例如，从左到右、从上到下扫描，找到第一个 1）。
• 准备一个队列 queue 用于 BFS，一个集合或列表 boundary 用于暂存第一个岛屿的边界水域。
• 准备一个 visited 二维数组（大小同 grid），用于记录 BFS 中已访问的格子，初始全为 false。

步骤 4.2：DFS 标记第一个岛屿并收集边界水域
从找到的第一个 1 开始 DFS：

• 将该格子的值从 1 改为 2，表示属于第一个岛屿。
• 遍历该格子的四个邻居：
  • 如果邻居是 1，递归进行 DFS。
  • 如果邻居是 0，说明这是一个边界水域格子，将其坐标加入 boundary。

DFS 完成后，boundary 中存储了所有与第一个岛屿相邻的 0 格子。

步骤 4.3：多源 BFS

• 将 boundary 中的所有格子加入 BFS 队列 queue，并在 visited 中标记这些格子为已访问。
• 初始化 distance = 0（因为从第一个岛屿的边界 0 开始，这些 0 还没有被翻转，所以距离从 0 开始计数更符合逻辑：当我们第一次扩展到 1 时，需要翻转的 0 的数量就是当前的层数）。
• 开始 BFS 循环：
  1. 获取当前队列的大小 size，表示当前层的格子数。
  2. 对当前层的每个格子，检查其四个方向的邻居：
     • 如果邻居在网格内且未被访问：
       • 如果 grid[neighbor] == 1，说明找到了第二个岛屿，返回 distance。
       • 如果 grid[neighbor] == 0，将其标记为已访问并加入队列。
  3. 当前层处理完后，distance++（准备进入下一层）。

第 5 步：为什么 BFS 的距离从 0 开始？

在步骤 4.3 中，distance 初始为 0。因为 BFS 的第一层是第一个岛屿直接相邻的水域（0），我们还没有翻转任何格子。当我们从这些水域扩展到下一层时，如果直接遇到了第二个岛屿的 1，那么需要翻转的 0 就是第一层的那些格子，即 distance 当前的值（0）不对应翻转数。实际上，当第一次遇到 1 时，当前的 distance 就是需要翻转的 0 的数量，因为 BFS 是从第一个岛屿的边界 0 开始计层的。
更准确的做法：在 BFS 循环开始时，如果从队列中取出的格子本身就是第二个岛屿的 1，则返回 distance。但我们的 BFS 队列初始化时只加入了 0，所以第一次遇到 1 一定是在扩展过程中。因此，当我们在扩展过程中遇到 1 时，distance 就是已经经过的 0 的层数，即需要翻转的数量。

为了清晰，我们可以这样调整：

• distance = 0。
• BFS 循环中，在处理完当前层所有格子后，distance++。
• 在检查邻居时，如果邻居是 1，立即返回 distance。
  这样，当我们从第一个岛屿的边界（第一层 0）扩展到下一个格子（可能是 0 或 1）时，如果邻居是 1，则 distance 为 1？不对，因为当前层（第一层 0）还没处理完？实际上，标准的 BFS 层数计数是：
  • 初始化队列为第一层（边界 0），distance = 0。
  • 每次处理一层前，如果当前层有格子是目标，则返回 distance。
  • 否则，处理完当前层所有格子后，distance++，然后进入下一层。
    但在这个问题中，我们的目标（第二个岛屿的 1）不会出现在队列初始化时（因为初始化只加了 0），所以我们可以：
  • 初始化队列为边界 0，distance = 1（因为要翻转这些 0 才能到达下一个格子）。
  • 然后 BFS 循环：每次从队列中取出一个格子，如果它是 1（第二个岛屿），返回 distance-1？这样容易混乱。

更标准的做法：

1. 标记第一个岛屿，收集其边界 0 到队列。
2. 初始化 step = 0。
3. BFS 循环：
   a. 遍历当前队列中的所有格子（当前层）。
   b. 对每个格子，检查其四个邻居：
   - 如果邻居是 1 且未被标记为第一个岛屿（即值仍为 1），返回 step。
   - 如果邻居是 0 且未访问，标记并加入队列。
   c. 当前层处理完后，step++。

这样，step 表示从第一个岛屿边界开始，经过的 0 的层数。当第一次遇到第二个岛屿时，step 就是需要翻转的 0 的数量。

举例说明：
grid = [[0,1],[1,0]]

• 第一个岛屿：左上角的 1（坐标 (0,1)），标记为 2。边界 0：只有 (0,0) 和 (1,1)？不对，(0,1) 的邻居：上(越界)、下(1,1)=0、左(0,0)=0、右(越界)。所以边界 0 为 (0,0) 和 (1,1)。
• BFS 队列初始化：[(0,0), (1,1)]，step=0。
• 第一层（step=0）：
  • 处理 (0,0)：邻居 (1,0)=1（未被标记，是第二个岛屿），返回 step=0？但显然需要翻转 1 个 0。所以有问题。
    问题在于：当我们从第一个岛屿的边界 0 开始时，这些 0 还没有翻转。如果从这些 0 直接扩展到第二个岛屿的 1，那么需要翻转的 0 就是这些边界 0 本身，数量为 1。但在我们的 BFS 中，当我们在处理 (0,0) 时，发现邻居 (1,0) 是 1，此时 step=0，但实际需要翻转 (0,0) 这个 0，所以应返回 step+1=1。

修正：
BFS 应该从第一个岛屿的陆地单元格开始，而不是从边界 0 开始。但题目要求桥必须由 0 翻转而成，所以距离应该只计算 0 的数量。因此，我们可以：

1. 标记第一个岛屿，同时将其所有陆地单元格加入 BFS 队列，并标记为已访问。
2. 初始化 distance = -1（因为从陆地开始，第一层扩展到的 0 才是需要翻转的）。
3. BFS 循环：
   a. 遍历当前队列中的所有格子（当前层）。
   b. 对每个格子，检查其四个邻居：
   - 如果邻居是 1 且未被标记为第一个岛屿（即值仍为 1），返回 distance+1？还是返回 distance？我们来看：
   - 当队列中是第一个岛屿的陆地时，distance=-1，扩展到的邻居如果是 1（第二个岛屿），则不需要翻转任何 0，应返回 0？但两个岛屿不直接相邻，所以这种情况不会发生（题目保证两个岛屿独立）。
   - 所以，第一次遇到第二个岛屿的 1 一定是在队列中包含 0 的时候。
   - 如果邻居是 0 且未访问，标记并加入队列。
   c. 当前层处理完后，distance++。

这样，当 BFS 扩展到第二个岛屿的 1 时，distance 就是已经经过的 0 的层数，即需要翻转的数量。

最终简化步骤（最清晰且常用的方法）：

1. DFS 找到第一个岛屿的所有单元格，并将其值改为 2。同时，将这些单元格加入 BFS 队列（作为 BFS 的起点）。
2. 初始化 step = 0。
3. BFS 循环：
   • 遍历当前队列中的所有单元格（当前层）。
   • 对每个单元格，检查四个方向的邻居：
     • 如果邻居是 1（即第二个岛屿），返回 step。
     • 如果邻居是 0，将其值改为 2（或标记为已访问），并加入队列。
   • 当前层处理完后，step++。

为什么返回 step？

• step 表示从第一个岛屿的陆地出发，向外扩展的层数。第一层扩展到的都是与第一个岛屿相邻的 0，需要翻转这些 0 才能到达第二个岛屿吗？不一定，可能第二层才是第二个岛屿。
• 当我们在 BFS 中第一次遇到 1（第二个岛屿）时，step 表示从第一个岛屿到该 1 所经过的 0 的层数，即需要翻转的 0 的数量。

以示例 2 验证：grid = [[0,1,0],[0,0,0],[0,0,1]]

• 第一个岛屿：只有一个单元格 (0,1)，改为 2，加入队列。
• BFS：
  • step=0：队列 [(0,1)]。处理 (0,1)：邻居 (0,0)=0 -> 改为2并入队； (0,2)=0 -> 改为2并入队； (1,1)=0 -> 改为2并入队。队列变为 [(0,0),(0,2),(1,1)]。
  • step=1：处理当前层：
    (0,0)：邻居 (1,0)=0 -> 改为2入队。
    (0,2)：邻居 (1,2)=0 -> 改为2入队。
    (1,1)：邻居 (2,1)=0 -> 改为2入队。
    没有遇到 1。
  • step=2：处理队列 [(1,0),(1,2),(2,1)]：
    (1,0)：邻居 (2,0)=0 -> 改为2入队。
    (1,2)：邻居 (2,2)=1 -> 找到第二个岛屿，返回 step=2。
    正确。

第 6 步：代码框架（伪代码）

function shortestBridge(grid):
    n = grid.length
    queue = []  # 用于 BFS
    found = false

    # 步骤 1：DFS 标记第一个岛屿，并将所有陆地加入队列
    for i in range(n):
        if found: break
        for j in range(n):
            if grid[i][j] == 1:
                dfs(i, j)  # 标记第一个岛屿为2，并将所有单元格加入队列
                found = true
                break

    # 步骤 2：多源 BFS
    step = 0
    directions = [(0,1),(0,-1),(1,0),(-1,0)]
    while queue not empty:
        size = queue.length
        for k in range(size):
            (x, y) = queue.pop(0)
            for (dx, dy) in directions:
                nx, ny = x+dx, y+dy
                if nx, ny 在网格内:
                    if grid[nx][ny] == 1:  # 找到第二个岛屿
                        return step
                    elif grid[nx][ny] == 0:  # 水域，标记为已访问并加入队列
                        grid[nx][ny] = 2
                        queue.append((nx, ny))
        step++

function dfs(x, y):
    if x, y 越界或 grid[x][y] != 1:
        return
    grid[x][y] = 2
    queue.append((x, y))
    dfs(x+1, y)
    dfs(x-1, y)
    dfs(x, y+1)
    dfs(x, y-1)

复杂度分析：

• 时间复杂度：O(n²)，每个单元格最多被访问两次（一次 DFS，一次 BFS）。
• 空间复杂度：O(n²)，队列和递归栈的空间。

这样，我们就通过 DFS 标记第一个岛屿 + 多源 BFS 找到了连接两个岛屿的最短桥，其长度就是需要翻转的 0 的最小数目。