LeetCode 934. 最短的桥

2025-05-20 HGNULB 约 16 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 934. 最短的桥

题意分析

给一个 $n \times n$ 的 01 矩阵，1 表示陆地、0 表示水。题目保证矩阵中恰好有两座岛（岛 = 四连通的 1 的极大连通块）。你可以把若干个 0 翻转成 1，求最少翻转多少个 0 才能让两座岛连成一片。

要什么：最少翻转数。每翻转一个 0 的代价都是 1，没有权重差异，这又是一个无权图上的最短路问题。答案等于两座岛之间「最短的水路」上水格子的数量。

「恰好有两座岛」这条保证极其重要。它意味着：找到第一个 1 之后，从它出发的连通块就是完整的第一座岛，剩下的所有 1 必然属于第二座岛。于是我们不需要给岛编号，也不需要判断「碰到的这个 1 是不是自己人」——只要在标记完第一座岛之后碰到任何一个未被标记的 1，它一定属于第二座岛。这条性质直接把实现难度砍掉一半。

建模的关键一步是识别多源 BFS。如果只从第一座岛的某一个格子出发做单源 BFS，得到的是「从该格子出发的最短路」，而题目要的是「从整座岛出发的最短路」——两座岛之间的最近点对可能出现在岛的任意位置。正确做法是把第一座岛的全部格子一起作为 BFS 的起点同时入队，这等价于在图上虚构一个超级源点连向岛的每一格，边权为 0。此后 BFS 的第 $d$ 层就是「距离第一座岛恰好 $d$ 步的水格子」。

约束透露的信号：$n$ 最大 100，格子总数 $10^4$。这个规模下 $O(n^2)$ 的两遍扫描（一遍 DFS 标记、一遍 BFS 扩散）绰绰有余；而「枚举第一座岛的每个格子与第二座岛的每个格子求曼哈顿距离最小值」这种 $O(n^4)$ 的做法不仅慢，而且是错的——曼哈顿距离忽略了路径可能被陆地阻挡，也忽略了「翻转的是格子数而非步数」这层语义差异。

边界：翻转数至少为 1（两座岛若相邻就会合并成一座，与「恰好两座岛」矛盾）；矩阵至少 2×2；答案不可能是 -1，但代码保留这个兜底返回值以防输入不满足保证。

解法：先标记第一座岛，再多源 BFS 拓展水域

核心思路

先看暴力：找出两座岛的全部格子，两两配对算曼哈顿距离，取最小值再减一。这个做法在开阔水域下碰巧能算对，但只要两岛之间隔着第三方陆地（本题保证只有两座岛，所以不会发生）或者需要绕行，结论就不成立；更根本的问题是它把「翻转格子数」和「直线距离」混为一谈。而且 $10^4$ 个格子两两配对是 $10^8$ 次运算，也不划算。瓶颈在于：它试图用几何公式代替真正的路径搜索。

正确的建模是把水格子看成图的节点，相邻格子之间有一条边权为 1 的边，然后求「第一座岛」到「第二座岛」的最短路。因为边权全为 1，BFS 即可。

于是整个算法分成泾渭分明的两个阶段。

第一阶段：找到并整体标记第一座岛。 按行列扫描，遇到第一个 1 就以它为起点做 DFS（或 BFS），把整个连通块的每一格都改写成 2，同时把每一格都推进队列。这里改写成 2 而不是 0 有两层用意：一是把「第一座岛」与「第二座岛」区分开，后续 BFS 碰到 1 就知道是对岸；二是 2 同时充当「已访问」标记，让 BFS 阶段不必再开一个 visited 数组。找到第一座岛后必须立刻用 foundFirst 标志跳出双层循环，否则会把第二座岛也一并标记，那就再也找不到终点了。

第二阶段：以整座岛为源做分层 BFS。 队列里此刻装的是第一座岛的全部格子，steps = 0。不变量是：

第 $d$ 轮出队的格子，都是「距离第一座岛恰好 $d$ 步」的格子；也就是说，从第一座岛走到它需要翻转 $d$ 个水格子。

扩展时对每个邻居分三种情况。若越界，跳过。若是 1，说明碰到了第二座岛——注意此时当前格子已经是第 steps 层，从第一座岛走到当前格子需要翻转 steps 个 0，而下一步直接踏上第二座岛不需要再翻转，所以答案正是 steps，立即返回。若是 0，把它改写成 2（入队即标记）并入队，成为下一层的格子。若是 2（第一座岛或已访问的水），跳过。

为什么第一次碰到 1 就是最优？BFS 按层扩散，先被访问的层距离更小；第 steps 层的某个格子首次触达第二座岛时，不可能存在一条更短的路径——否则那条路径的终点会在更早的层就被处理。这正是 BFS 求无权最短路的基本性质。

还要说清 steps 的语义为什么恰好等于翻转数。第 0 层是岛本身（不需要翻转），第 1 层是紧贴岛的水格子（翻转 1 个），第 $d$ 层是翻转 $d$ 个之后能到达的水格子。在第 $d$ 层的格子上发现邻居是第二座岛，意味着翻转了这 $d$ 个水格子之后两岛已相连，答案就是 $d$。返回的是 steps 而不是 steps + 1，这是本题最容易差一位的地方。

解题步骤

双层扫描找到第一个值为 1 的格子，调用 DFS 标记，随即用 foundFirst 终止扫描。为什么必须终止：不加这个标志，循环会继续走到第二座岛并把它也标记成 2，BFS 阶段就永远碰不到 1，最终返回 -1。这两层循环的条件里都带上 && !foundFirst，是最简洁的写法。

DFS 递归基是「越界或当前格不为 1」。为什么判 != 1 而不是 == 0：递归会重复走到已被改成 2 的格子，用 != 1 一并挡住 0 与 2 两种情况，一个条件顶两个。

DFS 中先把格子改成 2、推进队列，再向四个方向递归。为什么先改标记再递归：这是「入队即标记」在 DFS 上的对应写法，防止同一格子被相邻的四个方向重复展开导致指数级重复。

BFS 前 steps = 0，外层每轮先取 size = queue.size() 的快照。为什么要快照：内层循环会往队列追加下一层的格子，直接用 queue.size() 作条件会让层边界消失，steps 与距离的对应关系随之失效。

对四个方向依次检查：先判越界，再判是否为 1，最后判是否为 0。为什么顺序不能换：越界检查必须最先做，否则 grid[nr][nc] 直接数组越界；判 1 要早于判 0，因为碰到 1 就该立刻返回，没必要继续。

邻居为 1 时立刻 return steps。为什么不是 steps + 1：当前格子处在第 steps 层，意味着已经翻转了 steps 个水格子才走到这里；下一步踏上的是原本就存在的陆地，不消耗翻转次数。

邻居为 0 时改写成 2 并入队。为什么改写要与入队同时发生：若等到出队才标记，同一个水格子会被上下左右多个前驱重复入队，队列膨胀甚至重复计数。改写成 2 也让 visited 数组变得多余。

一层处理完 steps++；队列耗尽返回 -1。为什么保留 -1：题目保证有两座岛，这一行实际不会被执行，但它让函数在输入不满足保证时有明确行为，而不是掉进未定义状态。

以 具体用例 grid = [[0,1,0],[0,0,0],[0,0,1]] 走一遍，预期答案是 2。两座岛分别是单格 (0,1) 与单格 (2,2)。

第一阶段：按行扫描，(0,0) 是 0 跳过，(0,1) 是 1，触发 DFS。把 (0,1) 改成 2 并入队；向四个方向递归：(1,1) 是 0（不为 1，返回）、(-1,1) 越界、(0,2) 是 0、(0,0) 是 0，递归全部结束。foundFirst = true，双层循环立刻退出——注意 (2,2) 那个 1 没有被标记，这正是我们要的。
此时 grid = [[0,2,0],[0,0,0],[0,0,1]]，队列 = [(0,1)]。

第二阶段，steps = 0。
第 0 层（size = 1）：出队 (0,1)。检查四邻：
(1,1) 值为 0 → 改成 2，入队。
(-1,1) 越界 → 跳过。
(0,2) 值为 0 → 改成 2，入队。
(0,0) 值为 0 → 改成 2，入队。
本层结束，steps 变成 1。队列 = [(1,1), (0,2), (0,0)]，这三格都是「翻转 1 个 0 可到达」的位置。

第 1 层（size = 3）：
出队 (1,1)：四邻 (2,1) 是 0 → 改 2 入队；(0,1) 是 2 → 跳过；(1,2) 是 0 → 改 2 入队；(1,0) 是 0 → 改 2 入队。
出队 (0,2)：四邻 (1,2) 已是 2 → 跳过；(-1,2) 越界；(0,3) 越界；(0,1) 是 2 → 跳过。
出队 (0,0)：四邻 (1,0) 已是 2 → 跳过；(-1,0) 越界；(0,1) 是 2 → 跳过；(0,-1) 越界。
本层结束，steps 变成 2。队列 = [(2,1), (1,2), (1,0)]。

第 2 层（size = 3）：
出队 (2,1)：四邻 (3,1) 越界；(1,1) 是 2 跳过；(2,2) 值为 1 → 碰到第二座岛，立即返回 steps = 2。

答案 2，含义是翻转 (1,1) 与 (2,1)（或 (0,2) 与 (1,2) 等其他等长方案）这两个水格子即可连通两岛，与预期一致。

顺带验证「返回 steps 而非 steps + 1」：路径是 (0,1) → (1,1) → (2,1) → (2,2)，其中 (0,1) 属于第一座岛、(2,2) 属于第二座岛，中间真正需要翻转的只有 (1,1) 与 (2,1) 两格。而 (2,1) 恰好处在第 2 层，steps 此刻正是 2，一一对应。

代码实现

class Solution {
    // 先找到并标记第一座岛后，把整座岛边界作为多源 BFS 起点，这样 BFS 的层数天然就是翻转次数。
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int shortestBridge(int[][] grid) {
        int n = grid.length;
        Queue<int[]> queue = new ArrayDeque<>();
        boolean foundFirst = false;

        for (int r = 0; r < n && !foundFirst; r++) {
            for (int c = 0; c < n && !foundFirst; c++) {
                if (grid[r][c] == 1) {
                    markFirstIsland(grid, r, c, queue);
                    foundFirst = true;
                }
            }
        }

        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] pos = queue.poll();
                int r = pos[0];
                int c = pos[1];

                for (int[] d : DIRS) {
                    int nr = r + d[0];
                    int nc = c + d[1];

                    if (nr < 0 || nr >= n || nc < 0 || nc >= n) {
                        continue;
                    }
                    if (grid[nr][nc] == 1) {
                        return steps;
                    }
                    if (grid[nr][nc] == 0) {
                        grid[nr][nc] = 2;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
            steps++;
        }

        return -1;
    }

    private void markFirstIsland(int[][] grid, int r, int c, Queue<int[]> queue) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != 1) {
            return;
        }
        grid[r][c] = 2;
        queue.offer(new int[]{r, c});

        markFirstIsland(grid, r + 1, c, queue);
        markFirstIsland(grid, r - 1, c, queue);
        markFirstIsland(grid, r, c + 1, queue);
        markFirstIsland(grid, r, c - 1, queue);
    }
}

func shortestBridge(grid [][]int) int {
    // 先找到并标记第一座岛后，把整座岛边界作为多源 BFS 起点，这样 BFS 的层数天然就是翻转次数。
    n := len(grid)
    queue := make([][2]int, 0)
    dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
    foundFirst := false

    var dfs func(r, c int)
    dfs = func(r, c int) {
        if r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1 {
            return
        }
        grid[r][c] = 2
        queue = append(queue, [2]int{r, c})

        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    }

    for i := 0; i < n && !foundFirst; i++ {
        for j := 0; j < n && !foundFirst; j++ {
            if grid[i][j] == 1 {
                dfs(i, j)
                foundFirst = true
            }
        }
    }

    steps := 0
    head := 0
    for head < len(queue) {
        size := len(queue) - head
        for i := 0; i < size; i++ {
            cur := queue[head]
            head++
            r, c := cur[0], cur[1]

            for _, d := range dirs {
                nr, nc := r+d[0], c+d[1]
                if nr < 0 || nr >= n || nc < 0 || nc >= n {
                    continue
                }
                if grid[nr][nc] == 1 {
                    return steps
                }
                if grid[nr][nc] == 0 {
                    grid[nr][nc] = 2
                    queue = append(queue, [2]int{nr, nc})
                }
            }
        }
        steps++
    }

    return -1
}

复杂度分析

时间复杂度：$O(n^2)$。凭什么：第一阶段的扫描最多看 $n^2$ 个格子，DFS 只访问第一座岛的格子且每格一次；第二阶段的 BFS 中每个格子至多入队一次、出队一次（入队瞬间就被改写成 2，不会重复），出队时检查固定的四个方向。三部分都受格子总数 $n^2$ 约束，合计仍是 $O(n^2)$，即与输入规模同阶的线性。相比「两岛格子两两配对」的 $O(n^4)$ 快了两个数量级，而且那种做法本身还不正确。

空间复杂度：$O(n^2)$。凭什么：队列在最坏情况下（水域占满整张图）会同时容纳 $O(n^2)$ 个格子；DFS 的递归栈深度在岛呈蛇形时也能达到 $O(n^2)$。注意这里不需要额外的 visited 数组——把访问过的格子原地改写成 2，复用了输入矩阵本身，这是省下一整个 $O(n^2)$ 布尔数组的实用技巧（代价是修改了入参，若不允许则需先拷贝）。

关键点总结

「求最少操作数」且每次操作代价相同，一律先想 BFS。这道题的操作是「翻转一个 0」，代价恒为 1，于是最少翻转数就是无权图上的最短路。不要被「岛屿」二字带偏去想并查集或几何公式。

起点不是一个点而是一整个集合时，用多源 BFS。把整座岛的所有格子在第 0 层一次性入队，等价于虚构一个到岛上每格距离为 0 的超级源点。这个技巧在 994（多个腐烂橘子）、542（所有 0 作为源）、1162（所有陆地作为源）中反复出现，是网格 BFS 的第二形态。

用原矩阵的第三种取值同时充当「分组标记」与「已访问标记」，可以省掉 visited 数组。前提是这个值不会与输入取值冲突（这里 2 既不是 0 也不是 1），且题目允许修改入参。

「恰好两座岛」这类保证要主动用起来。有了它，第一座岛标记完之后剩下的 1 必然是对岸，判断条件从「这个 1 属于哪座岛」简化为「是不是 1」，代码短了一大截。读题时要专门找这类能砍掉分支的保证。

搜到目标时返回 steps 还是 steps + 1，取决于计数对象是「步数」还是「途中的格子数」。本题计的是翻转掉的水格子数，最后一步踏上的是原有陆地不计入，所以返回 steps。写之前先问一句「我数的到底是边还是点」。

找到第一座岛后必须立刻终止扫描。这是本题独有的坑：多扫一格就会把第二座岛也吞掉。用循环条件里的 && !foundFirst 比在循环体里 break 两层更简洁可靠。

面试视角：这题的标准答法是先说清「两阶段：DFS 圈出一座岛 → 以整座岛为源做多源 BFS」，再强调「BFS 层数即翻转数」和「第一次遇到 1 即最优」。面试官常见的追问有两个：一是「为什么不能直接算两岛最近格子的曼哈顿距离」——答「曼哈顿距离不考虑绕行，而且题目要的是格子数不是坐标差」；二是「第一阶段能不能也用 BFS」——答「可以，DFS 只是写起来更短；但如果岛可能非常大且形状狭长，DFS 的递归深度能到 $n^2$，用 BFS 或显式栈更稳」。能主动提到递归深度风险是加分项。

易错点总结

错误写法：找到第一座岛后不设 foundFirst，继续扫描并把所有 1 都标记掉 → 用例 grid = [[0,1],[1,0]]，两座岛都被改成 2，BFS 阶段永远碰不到 1，队列耗尽后返回 -1；正确答案是 1。

错误写法：碰到第二座岛时返回 steps + 1 → 用例 grid = [[0,1],[1,0]]，正确答案是 1，该写法返回 2。steps 已经计入了走到当前格子所翻转的水格子数，最后一步踏上的是原有陆地，不消耗翻转次数。

错误写法：只把第一座岛的某一个格子入队做单源 BFS → 用例 grid = [[1,1,1,0,0],[0,0,0,0,0],[0,0,0,0,1]]，若只从 (0,0) 出发，算出的距离会大于从 (0,2) 出发的真实最短距离，返回值偏大。两岛的最近点对可能落在岛的任意位置，必须整座岛作为多源起点。

错误写法：BFS 中先访问 grid[nr][nc] 再判越界 → 用例任意，只要岛贴着边界，nr 或 nc 取到 -1 或 n 时立刻数组越界异常。方向偏移之后的第一件事永远是边界检查。

错误写法：水格子出队时才改写成 2 → 用例 grid = [[1,0,0],[0,0,0],[0,0,1]]，同一个水格子会被上下左右多个前驱重复入队，队列规模膨胀，且同一格可能在不同层被重复计数，steps 与真实距离脱节。标记必须在入队的同一时刻完成。

错误写法：外层循环写成 for (int i = 0; i < queue.size(); i++) 而不取快照 → 用例 grid = [[0,1,0],[0,0,0],[0,0,1]]，本层扩展出的新格子混入当前层，steps 不再等于距离，返回值偏小。

错误写法：DFS 的递归基写成 grid[r][c] == 0 就返回 → 用例任意含多格的岛，已被改成 2 的格子不满足 == 0，会被重复展开并再次入队，队列里出现重复元素，且递归可能不终止。条件应当是 != 1，一次挡住 0 与 2。

错误写法：另开 boolean[][] visited 数组但忘记在 DFS 阶段也标记 → 用例 grid = [[1,1],[1,0]]，第一座岛的格子在 BFS 中被当作未访问的邻居反复处理；用「改写成 2」这一种机制统一表达访问状态，可以从根本上避免两套标记不同步。

错误写法：枚举两座岛的全部格子对，取曼哈顿距离最小值减一 → 用例 grid = [[0,1,0],[0,0,0],[0,0,1]]，(0,1) 与 (2,2) 的曼哈顿距离是 3，减一得 2 碰巧正确；但一旦两岛形状复杂、最近的一对格子之间隔着自家陆地需要绕行，公式就会给出偏小的结果。几何公式代替不了路径搜索。

错误写法：steps++ 写在内层循环体里 → 用例 grid = [[0,1,0],[0,0,0],[0,0,1]]，第 0 层展开三个邻居就把 steps 加了三次，返回值远大于真实的 2。层数按层递增，不按节点递增。

错误写法：把「第一座岛」标记成 0 → 用例任意，岛的格子会被 BFS 当成可扩展的水域重复入队，且再也无法区分陆地与水，整个算法失去意义。标记值必须是输入中不存在的第三种取值。

相似题目

题目	难度	考察点
200. 岛屿数量	中等	只需数连通块个数，用的是本题第一阶段那半套 DFS 标记，不涉及后续的距离扩散
695. 岛屿的最大面积	中等	DFS 要带返回值累加格子数，考的是递归函数如何向上汇总子结果
994. 腐烂的橘子	中等	多源 BFS 的最典型形态，起点是全部腐烂橘子，还要在结束后检查是否有格子没被覆盖
542. 01 矩阵	中等	同为多源 BFS，但要输出每个格子的距离而非单个最小值，答案是一整张距离表
1162. 地图分析	中等	多源 BFS 求的是最大距离而非最短，答案在队列耗尽时的最后一层
1020. 飞地的数量	中等	从边界反向 DFS 排除可逃脱的陆地，考的是「正难则反」的标记方向
130. 被围绕的区域	中等	同样从边界出发做标记，但要在最后统一回写两类不同的值
1254. 统计封闭岛屿的数目	中等	DFS 过程中要判断连通块是否触碰边界，需要在递归里传递一个「是否封闭」的标志
417. 太平洋大西洋水流问题	中等	从两组边界分别反向搜索再取交集，是「多源 + 多轮」搜索的组合形态
463. 岛屿的周长	简单	只需统计陆地格子与水或边界相邻的边数，一次遍历即可，不需要任何搜索