§1

题目描述

给定 n×n 的 0/1 网格 grid,其中恰好有两座四连通的岛。把最少数量的 0 改成 1,使两座岛连成一座,返回这个最少数量。

输入 = grid=[[0,1,0],[0,0,0],[0,0,1]]　输出 = 2

§2

思路解析动画文字版

记住「DFS 圈出第一座岛 → 多源 BFS 一圈圈扩水 → 撞到第二座岛时的层数就是答案」,下面逐帧套它。

从左上往右下扫,第一个遇到的陆地 1 在 (0,0)。就从它出发,用 DFS 把它所在的整座岛找全。

把 (0,0) 标记为第一座岛(绿),并放进 BFS 队列。接着沿四个方向继续 DFS,把同一座岛连着的 1 全找出来。

DFS 走到 (0,1),它和第一座岛连着,也标成绿、入队。第一座岛现在有 2 格。

DFS 走到 (1,1),它和第一座岛连着,也标成绿、入队。第一座岛现在有 3 格。

第一座岛一共 3 格,全部进了队列(绿)。它们将同时作为 BFS 的多个起点,一起向外扩水。下面开始一圈圈淹。

当前队列这 3 个格子离第一岛都是 0。看它们的邻居:是水就淹掉、新淹到的水离第一岛就是 1;若邻居是第二座岛的陆地,说明只填了 0 格水就接上了,答案就是 0。

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

往下的 (1,0) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。

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

往右的 (0,2) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。

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

往下的 (2,1) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。

往右的 (1,2) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。

当前队列这 4 个格子离第一岛都是 1。看它们的邻居:是水就淹掉、新淹到的水离第一岛就是 2;若邻居是第二座岛的陆地,说明只填了 1 格水就接上了,答案就是 1。

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

往下的 (2,0) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。

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

往右的 (0,3) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。

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

往下的 (3,1) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。

往右的 (2,2) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。

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

往右的 (1,3) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。

当前队列这 5 个格子离第一岛都是 2。看它们的邻居:是水就淹掉、新淹到的水离第一岛就是 3;若邻居是第二座岛的陆地,说明只填了 2 格水就接上了,答案就是 2。

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

往下的 (3,0) 是水(0),把它淹掉、标成已访问(蓝),加入下一圈队列。注意这只是 BFS 的访问标记;最终最短桥用了几格,等接通第二岛时由层数定,不是所有淹过的水都算在桥里。

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

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

往右看 (3,2),它是一块还没标记的陆地,正是第二座岛!说明扩到第 2 圈就接上了,要填的水格数就是 2,这就是答案。

回头看整趟:先一次 DFS 圈出第一座岛当多源起点,再用 BFS 一圈圈向外淹水,第一次淹到第二座岛时的圈数 2 就是最短桥。整个网格只走了常数遍,时间 O(n²)。

边界:隔一格填 1;对角不连通;多源 BFS 自然找最近通道。

两个追问:DFS 圈岛省事、BFS 保最短;标记后剩下的 1 必是第二岛。

§3

参考代码

from typing import Listfrom collections import dequeclass 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

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间：O(n²)，DFS 标记第一座岛、BFS 扩水各自最多把每个格子访问常数次,网格共 n² 格,合起来 O(n²)
空间：O(n²)，队列最坏装下接近一整张网格的格子,加上 DFS 的递归栈,都是 O(n²) 级

§5

易错点

✗ 错误写法：只圈一座岛却忘了「全部入队」

✓ 正确写法：DFS 标第一座岛时每格都要进 BFS 队列

多源 BFS 要从第一座岛的整圈边界同时往外扩,只放一个点会算出偏大的距离

✗ 错误写法：BFS 撞到第二岛时还 +1

✓ 正确写法：撞到第二座岛 1 立刻返回当前 steps

答案是「填的水格数」;碰到对岸陆地那一步不需要填,所以返回的是进入这一层前累计的 steps

✗ 错误写法：把第一座岛的格子重复当水填

✓ 正确写法：标记成 2(或单独 visited),只填值为 0 的格子

不标记会把已属第一岛的格子反复入队,既错又可能死循环

面试追问把动画讲成自己的话

追问为什么第一步用 DFS、第二步用 BFS,不统一?

第一步只是要把第一座岛「圈完」、不关心顺序,DFS 写起来最短;也完全可以用 BFS 或并查集圈岛。第二步要的是「最短距离」,必须用 BFS 逐层扩散才能保证第一次到达即最短,DFS 在这里不保证最短。两步各取所长。

追问怎么保证图里恰好只处理两座岛?

题目保证恰好两座岛。代码找到第一个 1 就 DFS 把它整座标记成 2,于是网格里剩下的 1 只属于第二座岛;BFS 扩水时一旦遇到值为 1 的格子,必然是第二座岛,直接返回即可,不会误判。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 图论套路 27/48

移除最多的同行或同列石头

LeetCode 947 · 中等 · 沿着图论套路继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

599道动画图解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

from typing import Listfrom collections import dequeclass 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

最短的桥

题目描述

思路解析动画文字版

参考代码

复杂度

易错点

面试追问把动画讲成自己的话

移除最多的同行或同列石头

把这道题真正学会，再走

最短的桥

题目描述

思路解析动画文字版

参考代码

复杂度

易错点

面试追问把动画讲成自己的话

移除最多的同行或同列石头

把这道题真正学会，再走