BFS 广度优先搜索：迷宫最短路

1 一句话问题

同样的网格，1 能走，0 是墙。从左上角 (0,0) 走到右下角 (n-1,m-1)， 每步只能上下左右移动一格，问最少要几步。走不到就输出 -1。

输入      3 3
          110
          011
          011
输出      4        (0,0)→(0,1)→(1,1)→(1,2)→(2,2)

2 先用纸笔手算一遍

这次换一种手算方式，请一定照做 —— 它就是 BFS 本身。

在起点写 0。然后：把所有「挨着 0 且能走」的格子写上 1； 再把所有「挨着 1 且还是空白」的格子写上 2；再写 3……

起点 0        第一圈 1        第二圈 2        第三圈 3
0 . .         0 1 .           0 1 2           0 1 2
. . .         . . .           . 2 .           3 2 3
. . .         . . .           . . .           . 3 .

写到终点被填上数字为止，那个数字就是答案。

注意你没有去枚举任何一条路径 —— 你只是一圈一圈往外涂。这就是 BFS。

3 暴力：DFS 枚举每一条路，取最短的

如果不知道上面那个涂色法，最直接的想法是：既然要「最短」，那把所有能走的路线都走一遍， 记下其中最短的。用第 13 章的 DFS 枚举，走过的格子标记上不再重复走（否则会绕圈子）， 从一条分支回来时再把标记撤销 —— 也就是第 3 章的回溯。

点「运行 ▶」看结果

4 实测：看它怎么爆炸

下面这个对比是这一章最重要的一个实验，请亲手做一遍。

先用默认的 6（一个 6×6 的空网格），点右上角的 「开始对比 ▶」 跑一次，记住暴力用了多久。 然后把「网格边长」框里的 6 改成 7，再点一次「开始对比 ▶」。

空网格上，从左上走到右下的路径条数是：

**边长只加了 1，工作量乘了 450 倍。**而 BFS 这边，6×6 是 36 个格子，7×7 是 49 个 —— 它压根没感觉到区别。

5 慢在哪

暴力的毛病不在「用了 DFS」，而在于它必须把每一条路都走到底才敢下结论。

可是那五亿条路里，绝大多数一眼就知道不可能是最短的 —— 绕远了、兜圈了。 暴力却老老实实一条条走完。

更根本地说：暴力是在「所有路径」这个集合里找最小值，而这个集合是指数大的。 但我们真正想要的只是一个数字（最短步数），根本不需要把路径都列出来。

6 ★ 关键的一步

dist[i][j] 的含义：从起点走到 (i,j) 的最短步数，-1 表示还没到过。 -1 同时充当了「未访问」标记 —— 一个数组干两件事。

7 BFS 写法

点「运行 ▶」看结果

BFS 的骨架永远是这四行，背下来：

dist[起点] = 0;  q.push(起点);
while (!q.empty()) {
    取出队首 u;
    for (u 的每个邻居 v)
        if (v 能走 && dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
}

8 按圈打印扩散过程

点「运行 ▶」看结果

对比第 13 章 trace.cpp 的输出：那边是一条越缩越深的线，这边是一层层齐头并进。 同样是搜索，一个用递归（栈），一个用队列 —— 差别全在这里。

9 单步看波纹扩散

**这是第 13 章那张一模一样的 8×8 地图。**建议开两个标签页，把两个动画放在一起播。

盯住这几件事：

• 颜色相同 = 距离相同 = 同一圈。你会看到清清楚楚的等距波纹。
• 右边的队列：队首出去，新格子从队尾进来。队列里的元素距离最多只差 1 —— 这就是 BFS 能保证按距离顺序处理的原因。
• 终点被涂上颜色的那一刻，动画立刻停止 —— 后面的格子根本不用算了。
• 和 DFS 对比：DFS 的访问顺序是一根线，BFS 是一圈圈的环。

10 ★ 对拍验证

必试的几个错误：

• 删掉 if (dist[x][y] != -1) continue; → 报超时。这就是上面说的「入队即标记」。
• 漏掉一个方向（比如把 d = 0 改成 d = 1，丢掉「向上」）→ 会被抓，但可能要几十轮
• 在出队时才判断终点，改成入队时就 break → 想想这样对不对，用对拍验证你的判断
• 起点终点是墙的情况 → 生成器强制了它们可走，试试手动改代码去掉那个特判

11 什么时候用 DFS，什么时候用 BFS

这是本章最该带走的判断力：

12 自测