LeetCode 934. 最短的桥

约 9 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 美团 滴滴
标签
数组 深度优先搜索 广度优先搜索 矩阵

题目描述

✅ 934. 最短的桥

image-20260928225335549

image-20260928225335550

题意分析

网格中恰好有两座四连通岛屿，需要把最少的水格 0 变成陆地，使两座岛连在一起。答案只统计翻转的水格，原有陆地不需要付出代价。

第一座岛内部本来就连通，从它的任何位置出发都不需要先翻水。因此应把整座岛作为起点集合，寻找它到另一座岛的最少水格距离。

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

核心思路

[!blue]

先找到任意一个陆地格，用显式栈遍历它所在的完整岛屿。每发现一个岛格就把它从 1 改成 2，并加入 BFS 队列。编号 2 表示已经发现；第一座岛全部标记后，网格中剩余的 1 就只能属于第二座岛。

BFS 的所有初始格子都来自第一座岛，距离均为 0。设正在处理的这一层对应 steps 次翻转：扩展到相邻水格时，需要再翻一个格子，所以它进入下一层；扩展到值为 1 的格子时已经到达第二座岛，陆地不用翻转，直接返回当前 steps。

队列按层处理，先搜索需要翻较少水格的位置，再搜索需要翻更多水格的位置。因此第一次碰到第二座岛，就已经找到了最少翻转数。水格在入队前立即改成 2，同一格只会由最早到达它的路径发现，不会重复入队。

每层开始时必须固定当前层的格子数量，扩展中加入的水格属于下一层，不能立刻混在这一层处理。Go 的队列保留了已处理的前缀，因此当前层大小使用 len(queue) - head。

解题步骤

  1. 扫描网格，找到第一块陆地后，用显式栈标记整座岛，并把它的全部格子加入 BFS 队列；不再寻找其他起点。
  2. 将 steps 初始化为 0，每轮先固定队列中尚未处理的当前层大小。
  3. 取出这一层的每个格子，检查上下左右，跳过越界位置。
  4. 相邻格为 1 时返回 steps；为 0 时先改成 2 再入队；为 2 时跳过。
  5. 当前层全部处理完后再令 steps++，继续扩展下一层水域。整个实现直接使用网格保存访问标记，会修改输入。

代码实现

class Solution {
    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) {
        Deque<int[]> stack = new ArrayDeque<>();

        grid[r][c] = 2;
        stack.push(new int[] {
            r,
            c
        });
        queue.offer(new int[] {
            r,
            c
        });

        while (!stack.isEmpty()) {
            int[] cell = stack.pop();

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

                if (nr < 0
                        || nr >= grid.length
                        || nc < 0
                        || nc >= grid[0].length
                        || grid[nr][nc] != 1) {
                    continue;
                }

                // 发现时立即标记，第一岛与海水扩展都不会重复加入同一格。
                grid[nr][nc] = 2;
                stack.push(new int[] {
                    nr,
                    nc
                });
                // 第一岛格子作为零距离起点；海水格则进入下一层。
                queue.offer(new int[] {
                    nr,
                    nc
                });
            }
        }
    }
}

func shortestBridge(grid [][]int) int {
    n := len(grid)
    queue := make([][2]int, 0)
    dirs := [][2]int{
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1},
    }
    foundFirst := false

    dfs := func(r, c int) {
        grid[r][c] = 2
        stack := [][2]int{
            {r, c},
        }
        queue = append(queue, [2]int{
            r,
            c,
        })
        for len(stack) > 0 {
            cell := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            for _, d := range dirs {
                nr, nc := cell[0]+d[0], cell[1]+d[1]
                if nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] != 1 {
                    continue
                }
                // 发现时立即标记，第一岛与海水扩展都不会重复加入同一格。
                grid[nr][nc] = 2
                stack = append(stack, [2]int{
                    nr,
                    nc,
                })
                // 第一岛格子作为零距离起点；海水格则进入下一层。
                queue = append(queue, [2]int{
                    nr,
                    nc,
                })
            }
        }
    }

    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)$。标记第一座岛和后续 BFS 都至多处理线性于网格总大小的格子，每个格子只检查四个方向。
  • 空间复杂度：$O(n^2)$，用于标记岛屿的显式栈和 BFS 队列，没有额外的递归栈或访问数组。

关键点总结

[!green]

  • 第一座岛的每个格子都是零代价起点，多源 BFS 同时从全部位置向外搜索。
  • BFS 层数表示已翻转的水格数，到达第二座岛时不再增加代价。
  • 入队前标记保证不重复扩展，按固定层大小处理保证距离含义不变。

易错点总结

[!yellow]

  • 只从第一座岛的某一个格子开始 BFS：最近的连接位置可能在岛的另一侧，整座岛都应作为距离 0 的起点。
  • 没有先完整标记第一座岛：搜索中遇到的 1 可能仍属于第一座岛，不能据此判断已经到达第二座岛。
  • 遇到第二座岛时返回 steps + 1：会把不需要翻转的终点陆地也算进去。
  • 一边入队一边改变当前层大小：新加入的水格会被提前处理，导致一次循环跨过多层。
  • 水格出队时才标记：它可能被同层的多个邻居重复加入队列，应在发现时立即标记。

相似题目

题目 难度 关联与区别
200. 岛屿数量 中等 先用连通遍历找到并标记第一座岛，才能把整座岛作为最短扩张的起点集合。
542. 01 矩阵 中等 同样多源BFS计算到目标集合的距离，本题从一座岛向外扩张直到碰到另一座岛。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/18390339
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！