第 14 章讲 BFS 时会用完全相同的 8×8 网格。 学完两章之后，把两个动画摆在一起看一遍 ——「深度优先」和「广度优先」的差别， 用看的比用背的清楚一百倍。
1 一句话问题
给一张 n × m 的网格，1 是陆地，0 是水。上下左右相邻的陆地算同一块。问一共有几块陆地。
输入 4 5
11000
11000
00100
00011
输出 32 先用纸笔手算一遍
拿铅笔在上面那张 4×5 的图上圈一圈：左上角 2×2 的四个格子是一块，
中间孤零零的 (2,2) 是一块，右下角 (3,3) (3,4) 是一块。共 3 块。
现在请注意你自己刚才是怎么圈的：你多半是把笔尖点在一个格子上， 然后顺着相连的格子一路滑过去，直到滑不动了才回头。
**这就是 DFS。**你的手已经会了，只是还没翻译成代码。
3 暴力：反复扫描整张图
假设你还不会 DFS。最自然的想法是：
找一个还没标记的陆地格，标记上，作为这一块的起点。 然后一轮一轮往外扩张 —— 每一轮扫描整张图，把所有「紧挨着已标记格子」的陆地也标记上。 某一轮下来一个新的都没有了，说明这块扩张完了，块数 +1，去找下一个起点。
点「运行 ▶」看结果
这个思路完全正确，而且朴素得让人放心。问题在第 5 步。
4 实测：它到底有多慢
小图上看不出问题。换一张 200×200 的「蛇形长廊」：整张图只有一块陆地， 但这一块被拉成了一条又长又绕的通道（长度约两万格）。点右上角的 「开始对比 ▶」。
在我的机器上：暴力约 1.0 秒，DFS 约 0.003 秒 —— 差了三百多倍。 把边长改成 240，暴力会涨到 2 秒多，而 DFS 纹丝不动。
5 慢在哪
慢在这一句：每往外扩张一层，就要把整张 n×m 的图重新扫一遍。
蛇形长廊的通道长约 L = 20000 格，所以要扫 20000 轮，每轮 40000 个格子 —— 八亿次操作。而整张图一共才 40000 个格子。
问题的根子在于暴力的姿态是被动的：它站在原地反复扫，等着陆地自己「长」过来。 可我们手算的时候明明不是这样 —— 我们是拿着笔主动滑过去的。
6 ★ 关键的一步
既然我站在一个陆地格上，我完全可以自己走过去，何必反复扫全图等它长过来？
走到一个格子 → 染上色 → 立刻从这个格子继续往四个方向走 → 走过的不再走。
「走到一个新格子，然后从这个新格子继续做同样的事」—— 这句话翻译成代码，就是函数调用自己。
于是每个格子只被访问一次：O(L × n × m) → O(n × m)。
dfs(i, j) 的职责（第 1 章的三要素，一个都不能少）：
| 要素 | 内容 |
|---|---|
| 职责 | 我站在格子 (i,j) 上，负责把所有和它连通的、还没染色的陆地全部染上色 |
| 边界 | 不用写显式的 return —— 当四个方向都「出界 / 是水 / 已染色」时，for 循环自然结束 |
| 递推 | 对四个方向的每个合法邻居 (x,y)，调用 dfs(x, y) |
第 1 章的递归有一行显眼的 if (n == 0) return 0;，DFS 里却好像找不到出口。
出口藏在那三个 continue 里：出界、是水、已经染过色。
这三个条件挡住了所有分支，for 循环走完，函数自然返回 —— 这就是边界。
其中「已经染过色」是最关键的那个。删掉它，两个相邻格子会互相无限调用， 瞬间栈溢出。第 10 步的对拍会让你亲眼看到这个后果。
7 DFS 写法
点「运行 ▶」看结果
注意主函数里的这个模式，它是所有连通块问题的通用骨架：
for (每个格子)
if (是陆地 && 还没染色) {
blocks++; // 每发起一次 dfs，就意味着发现了一块新的
dfs(i, j); // 这一次调用会把整块都染完
}「发起了几次 DFS」和「有几个连通块」是同一个数 —— 想明白这一点，这道题就通了。
8 把 DFS 的脚印打印出来
点「运行 ▶」看结果
读输出的时候找这两处：
- 缩进一路变深 —— 它顺着一个方向猛扎，走不动了才停。
- 出现
<- ... 退回上一层之后，上一层紧接着又往别的方向走了 —— 退回不是失败，是让上一层的 for 循环接着试下一个方向。
9 单步看 DFS 怎么走
换一张地图试试（1 = 能走，0 = 墙）
这张 8×8 地图和第 14 章的完全一样。播放时盯住：
- 格子里的数字是访问顺序。看它是怎么「拉成一条线」的 —— 不是一圈圈铺开。
- 右边那根递归栈，和第 1 章调用栈动画里的柱子是同一个东西，只是装的从数字变成了格子。
- 栈突然变矮的那些时刻，就是「一条道走到黑之后往回退」。
- 三块陆地用三种颜色 —— 每种颜色对应主函数里的一次
dfs调用。
10 ★ 对拍验证
把「DFS 版」那一栏换成你自己默写的，再点开始。
这几个错误几乎人人都犯过，故意试一次：
- 把
vis[i][j] = 1;那行删掉 → 相邻格子互相无限调用，对拍会报「超时」（其实是栈溢出） - 方向数组写成八连通（对角线也算相邻）→ 第 1 轮就被抓
- 漏掉一个方向（比如只写上下左） → 第 1 轮就被抓
- 忘了判断出界 → 数组越界，对拍会报「异常退出」
这里的生成器故意让陆地和水各占一半。如果陆地占 90%，整张图基本就是一大块， 那种数据太温柔，什么错都查不出来。
一半一半才会造出细长、分叉、犬牙交错的形状 —— 这才是能逼出 bug 的数据。 造数据的原则永远是：逼着程序走它平时不走的路。
11 一个必须知道的坑：递归深度
DFS 的递归深度最坏等于连通块的格子数。刚才那条 200×200 的蛇形长廊， 深度就有两万层。栈默认只有 8MB，一层几十字节，几万层还扛得住， 但如果是 1000×1000 的大图（最坏一百万层），程序会直接崩溃 —— 而且不报任何错。
竞赛里遇到大网格，有三条路：
- 改用 BFS（下一章），用队列代替递归栈，堆内存管够；
- 手写栈把递归改成循环；
- 在支持的评测机上开大栈空间。
入门阶段记住结论就行：网格大到几十万格以上时，优先用 BFS。
12 自测
- 洛谷 P1596 Lake Counting S —— 本章模板题，只是改成八连通 —— 改方向数组即可
- 洛谷 P1451 求细胞数量 —— 和本章几乎一模一样，先拿它练手
- 洛谷 P1162 填涂颜色 —— 要从「外面」往里染色 —— 想想为什么不能从里面开始
- 洛谷 P1706 全排列问题 —— 回头复习第 3 章：确认自己看得出它和本章是同一个 DFS
第 14 章用同一张地图问一个不同的问题：从左上角走到右下角最少要几步？ DFS 在这个问题上会彻底翻车（7×7 的空网格就要枚举五亿七千万条路）， 而 BFS 只需要扫一遍格子。