# 参考解 · lab 0021 · 搜索：把图走一遍

**做完四个任务再打开这里。** 这里的四个 `.py` 与任务目录里的文件同名：
把它们拷进 `lab/0021-dfs-bfs-search/` 覆盖同名文件，再跑 `py run_tests.py`，
应当四个任务全过（本机实测 4 秒上下，其中 DFS 那几段限量跑各占零点二秒）。

参考解是自包含的：`tools.py` 与 `run_tests.py` 这里各有一份，拷过去直接就能跑。
四个任务都只 `import` 给好的 `tools`，任务之间**不互相 import**，所以拷一个也能跑。
这与 0010、0017 那两套的约定一致。

## 逐个任务看什么

| 任务 | 参考解里补上的关键几行 | 要看的现象 |
| --- | --- | --- |
| 1 · 两套模板与两种走法 | DFS 用 `stack.pop()`、BFS 用 `q.popleft()`，两边的四行判断一模一样：不越界 → `not blocked[nr][nc]` → `not seen[nr][nc]` → **当场标记**；`dfs_walk_order` / `bfs_walk_order` 只是把弹出的点收进 `out` | 6×6 那张有墙的图上两套都数出 **29** 个格子（2500 格的 50×50 大图上两套都是 **2063**）；20 个点那张图上 DFS 次序是 `1 6 9 17 …`、BFS 是 `1 2 6 3 …`——**从第二个点就分开**，而走完的点数一样 |
| 2 · 迷宫最短路与 DFS 的代价 | `bfs_steps` 队列存 `(行, 列, 步数)`、出队判一次终点；`bfs_treasure` 队列存 `(行, 列, 步数, 捡到几个)`；三段 DFS 都是「标记 → 递归 → **收回 seen**」，`dfs_calls_limited` 每进一次 `walk` 就 `calls[0] += 1`、超过 `limit` 立刻 `return` | 15×15 那张迷宫（183 个能走的格子）BFS 给出 **56 步**，而 DFS 试到 **400001** 次还没试完、交回 `None`；空方格图上 DFS 的调用次数 **4×4 = 1271、5×5 = 90111**（与课件那两个数逐字一致），12×12 直接撞上限；宝箱那一题：56 步、捡到 **4** 个 |
| 3 · 岛屿数量、连通块与多起点 | `count_islands` 每遇到一块**没走过的陆地**就计数加一、再从那一格把整块走完；`count_components` 是「每个没去过的点起一次遍历」；`count_components_uf` 只有三行：`UnionFind(n)` + 逐条 `union` + `components()`；`reach_all` 把几个起点**全部先标 seen、一起入队** | 岛屿 4 / 5 / 4（对角线那两行里的 `1` 斜着挨着不算连着）；3000 个点、4002 条边的图搜索版与并查集版都是 **4** 块；多起点：迷宫四个起点里 `(7, 7)` 是墙，到达 **183**；50×50 大空图两个起点到达 **2500**（不是各走一遍相加的 5000） |
| 4 · visited 标记的时机 | 入队时标记那一支：`if not seen[nr][nc]: seen[nr][nc] = True; q.append(...); pushes += 1`；出队时标记那一支：入队时**不看 seen**、`pushes += 1`，等 `popleft` 出来 `if seen[r][c]: continue` 再标记 | 答案处处一样（6×6 都是 10 步、迷宫都是 56 步、60×60 都是 118 步），入队次数却一路拉开：6×6 网格 **36 → 119**（3.31 倍）、10×10 **100 → 359**（3.59）、20×20 **400 → 1519**（3.80）、迷宫 **144 → 453**；队列最长也跟着涨（100×100 上 **100 → 398**） |

## 每个任务的「为什么」

- **任务 1**：两套模板的差别**只有一行容器**——`stack.pop()` 换成 `q.popleft()`。
  四行判断完全一样，因为「能走到哪里」这件事与走的先后无关。
  次序差别才是重点：DFS 弹的是**最后压进去**的邻居，于是一条路走到黑；
  BFS 从队尾进、队头出，于是同一个点的邻居会连着被看到。
  所以 `dfs_walk_order` 与 `bfs_walk_order` 在第二位上就分开，而
  `dfs_reach` 与 `bfs_reach` 必须给出同一个数——判分两样都核。
  那段 DFS 写成**显式栈**不是省事，是必须：本课网格一条路就能走到几千格，
  递归的 1000 层上限（实际 998 层）根本不够。
- **任务 2**：这一段是全课的核心。BFS 的步数是**跟格子一起进队列**的：
  同一个时刻队列里可能同时有第 3 层和第 4 层的格子，用一个「当前第几层」
  的全局变量分不开。第一次把终点弹出队列时的那个步数就是最短的——
  这是「一层一层扩」的直接推论，也是 DFS 给不出的保证。
  DFS 那三段**必须把 `seen[r][c]` 收回来**（`seen[r][c] = False`），
  不然第一条路走到底就再也试不出第二条路，`best` 里那条常常不是最短的。
  `dfs_calls_limited` 的存在也是必要的：同一道题 4×4 只要 1271 次调用，
  12×12 按这个势头是几亿次，判分不可能等它——给它一个上限，
  看它撞上来就够了（本机 6×6 用 0.21 秒撞掉 40 万次）。
  宝箱那一题是同一套模板换一道题：**「捡了几个」也要跟着状态走**
  （`(行, 列, 步数, 捡到几个)`），顺手踩到的才算、不绕路。
- **任务 3**：岛屿与连通块是同一套模板的两种包装——网格上「遇到没走过的陆地
  就计数加一」对应图论上「遇到没去过的点就计数加一」，遍历的那一圈完全一样。
  斜着挨着不算连着，所以 `(0,0)` 与 `(1,1)` 是两块。
  并查集那一份**一行遍历都没有**：它只把每条边的两个端点合并，
  最后数还剩几个根。两条路数出来必须一样，这是两种数据结构的互证。
  多起点那一题的关键在「**共用**一张 seen」：几个起点先全部标上、一起入队；
  起点重复、或者两个起点本来就通着，都靠这一点处理——
  把每个起点的结果相加是错的（50×50 大空图上那样会得到 5000，实际 2500）。
- **任务 4**：把 `seen[nr][nc] = True` 从入队挪到出队，**答案不变、代价变四倍**。
  原因很具体：出队时标记意味着入队前不看 seen，同一个格子会被它的每个邻居
  各入队一次（最多四邻居），所以入队次数最多是点数的四倍，实测往 4 倍收敛
  （3.31 → 3.59 → 3.80，规模越大越接近）。顺带还有两个后果：
  队列最长从「一圈的长度」涨到四倍上下（100×100 上 100 → 398），
  出队时每个格子还要多判一次 `if seen: continue`。
  这一份里**出队时标记那一版是要保留的写法**（它是要看的对象，不是要改的错）；
  真正该记的规矩是：**入队（入栈）那一刻就标记**。

## 常见错法（对照自己的写法）

- **`blocked` 的 True 当成了「能走」**：写反了程序照样跑，答案全错。
  本课的口径与课件一致：`True` 是**不能走**（墙），`False` 是能走。
- **忘了 `not seen[nr][nc]`**：在有环的图上转不停（任务 1 那张 20 点的图里
  就有环，程序会一直跑下去）。DFS 用显式栈时这一条同样不能漏——
  只是「重复压栈」而已，不会爆栈，但会把一个点算好几遍。
- **DFS 不只标 `seen`、还把 `seen` 收不回来**：任务 2 的 `dfs_calls` 会
  交出一个明显偏小的调用次数（试不出第二条路），`best` 里的路往往偏长。
- **BFS 里另外维护一个「当前第几层」的变量**：同一时刻队列里有不同层的格子，
  这么写出的步数会忽大忽小；步数要跟格子一起进队列。
- **12×12 上硬等 DFS 跑完**：它是指数级的，等下去等不到。
  这一课要看的是「它跑不完」，所以任务里给的是带上限的版本，
  `dfs_calls_limited` 超过上限交回 `None`（**不是 -1**，-1 是「走不到」）。
- **多起点把每个起点的结果相加**：起点可能重复、也可能本来就通着，
  所以要一张共用的 seen。50×50 空图上相加会得到 5000，实际是 2500。
- **岛屿题里把斜着挨着的算成一块**：只有上、下、左、右四个方向算连在一起。
- **`count_components_uf` 里自己写遍历**：并查集这一份**不遍历**图，
  真写了遍历就看不出「两条路互证」这件事了；三行就够。
- **把 `bfs_trace` 的两个版本合成一个**：这一份要的就是「两版并存」的对照，
  合成一个就没得比了。
- **硬凑 `print` 后的数字**：判分读的就是那些行，硬凑等于没做。
  改完先自己跑 `py <任务文件>.py` 对一遍，再跑 `py run_tests.py`。

## 判分在读什么

判分不 import 学生代码来判（探针只用来试函数接口），它读的是**任务脚本自己打印的行**：

```text
任务 1   计数 01/02（6×6 上两套模板的到达数）、两套模板个数一致、
         次序 DFS / 次序 BFS 那两行、次序 点数一致吗、次序 第二个点一样吗、
         计数 03/04（50×50 大图两套的到达数）、大图 两套都走完、大图 两套都没超过总点数
任务 2   计数 01（迷宫 56 步）、迷宫 DFS 步数一致 / 交回 / 撞上限了吗、
         方格 4x4 / 6x6 / 8x8 / 12x12 四行（步数 + 调用次数 + 备注）、
         耗时 01/02（6×6）、倍数 01（5×5 的 90111 次）、5x5 的四行、
         宝箱两行、计数 04、12x12 的三行
任务 3   计数 01/02/03（三道岛屿题）、对角线 网格行数、计数 04/05（连通块两种数法）、
         连通块 两种数法一致、耗时 01/02、两条路各量一次 答案仍一致、
         计数 06（迷宫多起点）、四行「起点 … 是墙吗」、计数 09、
         计数 07、点边列表 单起点对照、计数 08
任务 4   计数 01/02（6×6 两版的入队次数）、6x6 两版答案一致、
         6x6 两版那一对「入队次数 队列最长」、倍数 01、
         方格 6x6 / 10x10 / 20x20 各四行（两版答案一致 + 计数 10/11 + 队列最长 + 倍数）、
         迷宫两行、60x60 三行、队列最长 100×100 两行、耗时 01/02
```

留白版原样跑是不通过的（本机实测 **21 PASS / 87 FAIL、退出码 1，0 处 Traceback**）：
两套模板都只交回起点、次序两行都是 `[]`、迷宫步数 `-1`、DFS 调用次数 `0`、
岛屿与连通块全是 `0`、四类入队次数与耗时全是 `0` / `0.000000`。
那是起点，不是 bug——**每一条 FAIL 都点出了缺哪一段 TODO**。

判分另有**探针进程**，它们 import 你的任务文件、拿判分**自己搭的图**去试函数：
任务 1 试 5×5 空图、1×1 单点图、判分自己砌的 7×7 带墙图、
一张 6 点的环图（带一个走不到的孤点）；
任务 2 试判分自己砌的迷宫、4×4 / 6×6 / 12×12 空方格图、「起点就是终点」、
一堵竖墙隔开的两半、4×4 与 5×5 上 DFS 的调用次数、`dfs_calls_limited`
在上限够大与不够大两种情形下的交回值；
任务 3 试全海 / 全陆 / 单格三张岛屿图、9 个点的小图（3 块 + 2 个孤点）、
「一条边都没有」、「一条链」、多起点的三种情形；
任务 4 试判分自己搭的 6×6 / 10×10 / 20×20 空方格图、有墙的 6×6、
一堵竖墙隔开的两半。

**DFS 那几项一律限量**：课件里 6×6 空方格的 DFS 要跑 9.68 秒、
1847 万次调用，所以判分只在小规模上核它的**精确**调用次数
（4×4 = 1271、5×5 = 90111，两个确定值都来自课件），
更大的规模一律走带上限的版本、只看它有没有撞上限。

判分看趋势不看常数：秒数换台机器就变，别背；入队次数、调用次数、
到达个数、岛屿数与连通块数都是**确定值**，那些是精确判的。

## 做完之后用一句话回答

「求最少步数为什么必须用 BFS、而 visited 为什么要在入队那一刻就标记」——
说清「一层层扩才能保证第一次到达就是最短」与「出队才标记会让同一个格子被
每个邻居各入一次、代价涨到近四倍，而答案一点不变」，就算这一课练到位了。