第 14 章的 BFS 你已经会了：一个起点，一圈圈往外扩，第一次到达即最短。
这一章的两个变形，BFS 的代码几乎一个字都不用改：
- 多源 BFS：起点不止一个。改动只有「初始化时把所有起点一起入队」这一句。
- 状态图搜索：根本没有网格。改动只有「用什么当作图上的点」。
第 2 项是这一章真正值钱的东西 —— 图不一定要画出来。 想清楚「什么是一个状态」，BFS 就能上。
前半场 · 多源 BFS
1 一句话问题
一张地图，. 是空地、# 是墙、F 是火源（可能有很多个）。
火每秒向上下左右蔓延一格，穿不过墙。问每个格子在第几秒被烧到。
输入 3 4
F..#
....
..#F
输出 0 1 2 -1 墙输出 -1
1 2 2 1
2 3 -1 02 暴力：每个火源跑一次 BFS
最直接的想法：有 k 个火源，就跑 k 次单源 BFS，每次更新全图的最小值。
点「运行 ▶」看结果
O(k · n · m)。完全正确，但火源一多就废了 ——
极端情况下 k = n·m，直接变成 O((nm)²)。
3 实测
| 地图 | 火源数 | 每个火源跑一次 | 多源一次跑完 |
|---|---|---|---|
| 100×100 | 约 200 | 0.03 秒 | 0.004 秒 |
| 200×200 | 约 800 | 0.52 秒 | 0.006 秒 |
| 300×300 | 约 1 800 | 2.58 秒 | 0.01 秒 |
注意暴力那一列的增长速度：地图边长翻倍，它慢了 8 倍（面积 ×4，火源数 ×4）。
4 ★ 关键的一步
把所有火源一次性全塞进队列，距离都设成 0，然后照常 BFS。
for (每个格子)
if (是火源) { d[i][j] = 0; q.push({i, j}); } // ← 唯一的改动
// 后面的 BFS 一个字都不用改为什么这样是对的？
回想 BFS 的本质（第 14 章）：队列里的元素按距离单调不减排列， 所以第一次到达某个格子时，距离一定是最小的。
一开始队列里就是所有距离为 0 的格子（那 k 个火源）—— 这个性质仍然成立。 之后弹出它们、扩展出距离 1 的一圈，再扩展出距离 2 的一圈…… 每个格子第一次被访问时，它到「离它最近的那个火源」的距离就定下来了。
还有个更好懂的说法：想象在地图外面加一个超级源点， 它到每个火源的距离是 0。那么「到最近火源的距离」就等于「到超级源点的距离」—— 多源问题被翻译成了单源问题。
复杂度：O(n·m)，和只有一个火源时一模一样。
点「运行 ▶」看结果
如果不同格子的通过代价不一样（比如走草地 1 秒、走沼泽 3 秒）， BFS 的「单调不减」就不成立了，多源这一招也跟着失效。
那时候要用的是多源 Dijkstra（第 32 章）—— 思路一样（所有源点距离设 0 一起入堆）， 但队列要换成优先队列。这个「多源」技巧是通用的，换的只是容器。
5 单步看几处火一起烧
换一张地图（. 空地，# 墙，F 火源）
这个动画一层一帧（而不是一格一帧），因为 BFS 的本质就是按层扩展：
- 第 0 帧：所有火源同时点亮 —— 这就是和单源 BFS 唯一的区别。
- 之后每一帧，所有距离相同的格子同时被烧到。
- 看两团火的波纹撞在一起：撞上的地方就停住了，因为那些格子已经被更近的火源占了。
试着在地图里多加几个 F，或者把中间的墙拆掉，看波纹形状怎么变。
6 ★ 对拍验证
值得故意写错的：
- 只把第一个火源入队 → 退化成单源，其他区域的答案偏大
- 入队时不设
d = 0，等出队再设 → 同一个火源可能被重复入队（第 14 章讲过） - 忘了处理「没有火源」 → 队列一开始就空，要保证输出全是 -1
- 墙的位置输出成 0 而不是 -1 → 边界处理
后半场 · 状态图搜索：八数码
7 一句话问题
3×3 的格子里放着 1~8 八个数字和一个空格，每次可以把和空格相邻的一个数字挪进空格。 问最少几步能拼成目标状态。
输入 283104765 2 8 3 目标： 1 2 3
1 . 4 8 . 4
7 6 5 7 6 5
输出 4（0 表示空格。九个数字按从上到下、从左到右写成一行。）
8 ★ 关键的一步：什么是「图上的一个点」
第 14 章的 BFS 走在网格上：
- 点 = 一个格子
- 边 = 上下左右挪一步
这道题看着完全不同 —— 没有网格，是一个拼图。但换个眼光：
- 点 = 整个棋盘的一种摆法（一个 9 位字符串，比如
"283104765"） - 边 = 把空格和相邻某一块交换一次（每个状态最多有 4 条边）
于是「最少几步拼好」就是「从起点状态走到目标状态的最短路」—— 一张不折不扣的图，虽然它长得不像图。
BFS 原封不动就能用。
唯一要改的是「访问标记」：网格用 vis[i][j] 数组，
而状态是字符串，所以改用 unordered_map<string, int> 记距离。
图不一定要画出来。
只要你能说清楚两件事：
- 什么是一个状态？（棋盘摆法 / 水壶里的水量 / 人在哪+钥匙拿了哪些）
- 从一个状态，一步能变到哪些状态？
那么 BFS（求最少步数）和 DFS（求方案）就都能上。
八数码、倒水问题、跳马、推箱子、魔方…… 全都是这一个套路。 考场上遇到「最少操作多少次」的题，先问自己这两句 —— 很多看起来无从下手的题，一下子就变成模板题了。
点「运行 ▶」看结果
九个数字的排列一共 9! = 362 880 种。听着不少，但对计算机来说是小数目 —— BFS 最多访问这么多状态，每个状态处理 4 条边，转眼就跑完。
而且实际上远远用不了这么多：从目标出发几步之内的局面，几百个状态就找到了。
（顺带一提：这 36 万个局面里，恰好一半是无解的 —— 它们和目标之间存在一个叫「逆序对奇偶性」的不变量，永远跨不过去。 想深究可以查「八数码可解性判定」，本章不展开。）
9 看它是怎么一层层铺开的
点「运行 ▶」看结果
以 283104765 为例，每层的新状态数是 1, 4, 8, 8, 16 —— 按层成倍地涨。
这就是搜索题的常态：层数每深一层，工作量翻好几倍。 所以第 16 章的剪枝、第 18 章的双向 BFS 才那么值钱 —— 它们要么砍掉一整片分支，要么把「一棵深树」变成「两棵浅树」。
10 ★ 对拍：用完全不同的搜索方式
拿什么给 BFS 对拍？再写一份 BFS 是没用的 —— 错了会一起错。
这里用迭代加深 DFS：限定深度做 DFS，找不到就把深度上限 +1 重来。 第一次搜到目标时，深度上限就是最短步数。
它和 BFS 的机制完全不同（几乎不用内存，但会重复搜）， 却必须给出同一个答案 —— 这才是有意义的交叉验证。
（迭代加深是第 18 章的主角，这里先借来当标准答案用。）
随机打乱九个数字，有一半的概率造出无解局面。
所以这里改成：从目标状态出发，随机走若干步。这样：
- 一定有解（原路走回去就行）
- 最优步数不超过走的步数，对拍跑得快
「按照解法反过来造数据」是个通用技巧， 特别适合那些「随机造出来大概率不合法」的题目（迷宫、拼图、合法括号串……）。
值得故意写错的：
dist判重写在出队时而不是入队时 → 同一个状态被重复入队，慢且可能超时- 忘了判重 → 状态无限循环，直接爆内存
- 找到目标时不立刻返回 → 答案还是对的，但会把整张状态图跑完
- 空格移动的越界判断写错（比如允许从第 0 列往左） → 字符串下标错位，答案乱掉
11 小结：BFS 的三种面孔
| 点是什么 | 边是什么 | 判重用什么 | |
|---|---|---|---|
| 网格最短路（第 14 章） | 一个格子 | 上下左右一步 | vis[i][j] 数组 |
| 多源扩散（本章前半） | 一个格子 | 上下左右一步 | 同上，只是初始入队多个 |
| 状态图（本章后半） | 一个「局面」 | 一次合法操作 | map / unordered_map |
BFS 的代码骨架从头到尾没变过：
起点入队并标记 → 反复取队首 → 扩展所有邻居 → 没访问过的标记 + 入队变的只是「点是什么」「邻居是什么」「拿什么记访问过」。 把这三个问题想清楚，任何 BFS 题都是模板题。
12 自测
- 洛谷 P1332 血色先锋队 —— 多源 BFS 模板题，本章前半场的原题
- 洛谷 P1443 马的遍历 —— 单源 BFS，但邻居有 8 个方向。先把「邻居是什么」想清楚
- 洛谷 P1379 八数码难题 —— 本章后半场原题。BFS 能过，学完第 18 章可以回来用双向 BFS 再写一遍
- 洛谷 P1135 奇怪的电梯 —— NOIP2007。状态是「在第几层」，边是「上 K[i] 层或下 K[i] 层」—— 典型的状态图 BFS
第 16 章 DFS 剪枝：可行性剪枝、最优性剪枝、搜索顺序。
第 4 章 N 皇后已经用过最基础的剪枝了。第 16 章会把它系统化 —— 搜索题的分数几乎全部来自剪枝，而剪枝的三板斧是可以套路化的。