最短的桥 图解题解

这道题到底在问什么

输入

grid=[[0,1,0],[0,0,0],[0,0,1]]

输出

2

先想最直接的笨办法

轮到队首 (0,0)(紫),挨个看它的四个邻居:是水(0)就淹、是没标记的陆地就说明到了第二座岛。（动画第 10 步）

最优解：一步一步想明白

1. 3记住「DFS 圈出第一座岛 → 多源 BFS 一圈圈扩水 → 撞到第二座岛时的层数就是答案」,下面逐帧套它。
2. 4从左上往右下扫,第一个遇到的陆地 1 在 (0,0)。就从它出发,用 DFS 把它所在的整座岛找全。
3. 5把 (0,0) 标记为第一座岛(绿),并放进 BFS 队列。接着沿四个方向继续 DFS,把同一座岛连着的 1 全找出来。
4. 6DFS 走到 (0,1),它和第一座岛连着,也标成绿、入队。第一座岛现在有 2 格。
5. 7DFS 走到 (1,1),它和第一座岛连着,也标成绿、入队。第一座岛现在有 3 格。
6. 8第一座岛一共 3 格,全部进了队列(绿)。它们将同时作为 BFS 的多个起点,一起向外扩水。下面开始一圈圈淹。
7. 9当前队列这 3 个格子离第一岛都是 0。看它们的邻居:是水就淹掉、新淹到的水离第一岛就是 1;若邻居是第二座岛的陆地,说明只填了 0 格水就接上了,答案就是 0。
8. 10轮到队首 (0,0)(紫),挨个看它的四个邻居:是水(0)就淹、是没标记的陆地就说明到了第二座岛。
9. 11往下的 (1,0) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。
10. 12轮到队首 (0,1)(紫),挨个看它的四个邻居:是水(0)就淹、是没标记的陆地就说明到了第二座岛。
11. 13往右的 (0,2) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。
12. 14轮到队首 (1,1)(紫),挨个看它的四个邻居:是水(0)就淹、是没标记的陆地就说明到了第二座岛。
13. 15往下的 (2,1) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。
14. 16往右的 (1,2) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。
15. 17当前队列这 4 个格子离第一岛都是 1。看它们的邻居:是水就淹掉、新淹到的水离第一岛就是 2;若邻居是第二座岛的陆地,说明只填了 1 格水就接上了,答案就是 1。
16. 18轮到队首 (1,0)(紫),挨个看它的四个邻居:是水(0)就淹、是没标记的陆地就说明到了第二座岛。
17. 19往下的 (2,0) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。
18. 20轮到队首 (0,2)(紫),挨个看它的四个邻居:是水(0)就淹、是没标记的陆地就说明到了第二座岛。
19. 21往右的 (0,3) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。
20. 22轮到队首 (2,1)(紫),挨个看它的四个邻居:是水(0)就淹、是没标记的陆地就说明到了第二座岛。
21. 23往下的 (3,1) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。
22. 24往右的 (2,2) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。
23. 25轮到队首 (1,2)(紫),挨个看它的四个邻居:是水(0)就淹、是没标记的陆地就说明到了第二座岛。
24. 26往右的 (1,3) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。
25. 27当前队列这 5 个格子离第一岛都是 2。看它们的邻居:是水就淹掉、新淹到的水离第一岛就是 3;若邻居是第二座岛的陆地,说明只填了 2 格水就接上了,答案就是 2。
26. 28轮到队首 (2,0)(紫),挨个看它的四个邻居:是水(0)就淹、是没标记的陆地就说明到了第二座岛。
27. 29往下的 (3,0) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。
28. 30轮到队首 (0,3)(紫),挨个看它的四个邻居:是水(0)就淹、是没标记的陆地就说明到了第二座岛。
29. 31轮到队首 (3,1)(紫),挨个看它的四个邻居:是水(0)就淹、是没标记的陆地就说明到了第二座岛。
30. 32往右看 (3,2),它是一块还没标记的陆地,正是第二座岛!说明扩到第 2 圈就接上了,要填的水格数就是 2,这就是答案。
31. 33回头看整趟:先一次 DFS 圈出第一座岛当多源起点,再用 BFS 一圈圈向外淹水,第一次淹到第二座岛时的圈数 2 就是最短桥。整个网格只走了常数遍,时间 O(n²)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from collections import deque
class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid)
        q = deque()
        def dfs(r, c):
            if r < 0 or r >= n or c < 0 or c >= n or grid[r][c] != 1:
                return
            grid[r][c] = 2
            q.append((r, c))
            dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
        found = False
        for r in range(n):
            if found: break
            for c in range(n):
                if grid[r][c] == 1:
                    dfs(r, c); found = True; break
        steps = 0
        while q:
            for _ in range(len(q)):
                r, c = q.popleft()
                for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n:
                        if grid[nr][nc] == 1:
                            return steps
                        if grid[nr][nc] == 0:
                            grid[nr][nc] = 2
                            q.append((nr, nc))
            steps += 1
        return -1

#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
    int shortestBridge(vector<vector<int>>& grid) {
        int n = grid.size();
        queue<pair<int,int>> q;
        function<void(int,int)> dfs = [&](int r, int c) {
            if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1) return;
            grid[r][c] = 2; q.push({r, c});
            dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
        };
        bool done = false;
        for (int r = 0; r < n && !done; ++r) for (int c = 0; c < n; ++c) if (grid[r][c] == 1) { dfs(r, c); done = true; break; }
        int dirs[5] = {1,0,-1,0,1};
        for (int steps = 0; !q.empty(); ++steps) {
            for (int sz = q.size(); sz--; ) {
                auto [r, c] = q.front(); q.pop();
                for (int d = 0; d < 4; ++d) {
                    int nr = r + dirs[d], nc = c + dirs[d+1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                        if (grid[nr][nc] == 1) return steps;
                        if (grid[nr][nc] == 0) { grid[nr][nc] = 2; q.push({nr, nc}); }
                    }
                }
            }
        }
        return -1;
    }
};

import java.util.*;
class Solution {
    int[][] grid;
    int n;
    Queue<int[]> q;
    public int shortestBridge(int[][] grid) {
        this.grid = grid; n = grid.length; q = new ArrayDeque<>();
        boolean done = false;
        for (int r = 0; r < n && !done; r++) for (int c = 0; c < n; c++) if (grid[r][c] == 1) { dfs(r, c); done = true; break; }
        int[] dirs = {1,0,-1,0,1};
        for (int steps = 0; !q.isEmpty(); steps++) {
            for (int sz = q.size(); sz > 0; sz--) {
                int[] cur = q.poll();
                for (int d = 0; d < 4; d++) {
                    int nr = cur[0] + dirs[d], nc = cur[1] + dirs[d + 1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                        if (grid[nr][nc] == 1) return steps;
                        if (grid[nr][nc] == 0) { grid[nr][nc] = 2; q.offer(new int[]{nr, nc}); }
                    }
                }
            }
        }
        return -1;
    }
    private void dfs(int r, int c) {
        if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1) return;
        grid[r][c] = 2; q.offer(new int[]{r, c});
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
    }
}

复杂度

面试官可能追问