拿到这本《王道论坛计算机考研机试指南》的时候，我已经把前六章的题刷得七七八八。真正让我卡住的，是第七章。这一章讲的是搜索——BFS、DFS、回溯、剪枝，听起来都是课本上很基础的名词，但机试里真正拉开差距的，恰恰是把这些基础玩出花来的能力。如果你也正在准备计算机考研的复试上机，或者刚接触在线评测系统，希望能用最短的时间搞懂搜索，这篇笔记就是按我实际读第七章的顺序整理的。第七章不是让你背三个模板就完事，它是让你从“暴力想不到”变成“暴力也有章法”。
1. 第七章的定位：为什么机试必须啃下搜索
1.1 从目录看这一章的野心
原书第七章的标题是“搜索”。我当时心里是有点意外的，搜索不是数据结构里的内容吗？怎么单独占一整章？后来刷题才明白，机试中的搜索不是一个孤立的算法，而是一整套思维方法：怎么描述状态、怎么扩展状态、怎么从“所有可能”里挑出有效路径。这一章反复强调四件事：状态、判重、剪枝、恢复现场。这四个词几乎能覆盖机试里大部分搜索题。
一开始我看目录觉得内容不多，BFS一节、DFS一节、回溯和剪枝再各一节，好像很好搞定。真正做题才发现，每一节背后都是十几个变形。比如BFS可以用于迷宫最短路径，也可以用于隐式图搜索，比如倒水问题；DFS可以用于连通块计数，也可以用于全排列、八皇后、数独。第七章表面在讲几个模板，实际是在训练你一种“翻译能力”：把题目描述翻译成状态空间里的节点和边。
1.2 搜索题在机试里的出场姿势
搜索题在机试中出现的频率非常高，经常是整套卷子里第二、第三题的位置。常见的场景有迷宫里找最短路径、地图上数连通块、给你几个数做全排列、八皇后、数独、倒水问题、单词接龙。这类题看起来千差万别，但本质都是一个东西：在一个有向的状态空间里找目标。
很多同学（包括我一开始）觉得搜索就是暴力，把每种情况都走一遍。这句话没错，但机试的难点从来不在于“知道该暴力”，而在于“怎么暴力得又快又不挂”。暴力裸搜大概率超时，怎么减少无效分支？状态太多怎么存？这就是第七章真正要解决的问题。所以它放在数据结构之后、图论之前，是因为搜索要用到队列、栈、树这些基础结构，同时又是后面最短路径、记忆化搜索这些内容的思想基石。
1.3 我的阅读路线
我第一遍只看了BFS和DFS，因为这两块模板性最强，看完就能上手写题。第二遍再回过头啃回溯和剪枝，这部分更需要做题来建立手感。我建议第一遍阅读时不要急着过完所有小节，先把BFS模板抄下来，找两三道迷宫题跑通，再继续往下走。搜索这个东西，看十遍不如自己调一遍bug。
这一章的章节顺序安排是合理的，但我不建议完全照顺序读。你可以按“模板先行 + 变体练习”的思路来：先掌握BFS和DFS的基本写法，再用后面的回溯和剪枝去处理变体题。这样不容易晕，也不会出现“书看懂了、题还是不会”的尴尬。
2. BFS：先见先出，把层数当成路径长度
2.1 一句话理解BFS
BFS用队列维护“当前层”的所有节点，每次从队首取出一个节点，把它能到达的下一层节点从尾部入队。因为先进先出，所以同一层的节点一定比下一层先被访问。第一次访问到某个节点时的步数，就是从起点到这个节点的最短步数。这是BFS最重要的性质，也是机试里最短路径类问题的基础。
为什么第一次到达就是最短？你可以想象一圈一圈地向外扩散，起点是第一圈，一步能到的点是第二圈，两步能到的点是第三圈。队列永远是按圈数从小到大的顺序取节点的，所以某个点第一次被碰到时，一定是它所在的圈数第一次被扩展到。这个直觉比背结论有用得多。
2.2 一个可以直接抄的迷宫模板
先看一个最经典的场景：二维迷宫，有墙有路，从S到E，求最短步数。这是一个标准的BFS，代码模板如下：
#include <iostream> #include <queue> #include <cstring> using namespace std; const int MAXN = 105; char mp[MAXN][MAXN]; int step[MAXN][MAXN]; int n, m; int sx, sy, ex, ey; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; struct Node { int x, y; }; void bfs() { memset(step, -1, sizeof(step)); queue<Node> q; q.push({sx, sy}); step[sx][sy] = 0; while (!q.empty()) { Node cur = q.front(); q.pop(); if (cur.x == ex && cur.y == ey) return; for (int i = 0; i < 4; i++) { int nx = cur.x + dx[i]; int ny = cur.y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (mp[nx][ny] == '#') continue; if (step[nx][ny] != -1) continue; step[nx][ny] = step[cur.x][cur.y] + 1; q.push({nx, ny}); } } } int main() { cin >> n >> m; for (int i = 0; i < n; i++) cin >> mp[i]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (mp[i][j] == 'S') sx = i, sy = j; if (mp[i][j] == 'E') ex = i, ey = j; } bfs(); cout << step[ex][ey] << endl; return 0; }这个模板里最关键的不是队列怎么写，而是step[nx][ny] != -1这个判重。我见过很多人把判重放在出队的时候，也就是取出队首节点后才判断是不是访问过，这样会导致同一个节点被大量重复入队，极端数据下直接MLE。正确做法是在邻居入队的那一刻就标记，保证每个状态最多只进队列一次。
2.3 状态设计比队列更重要
BFS模板十分钟就能背下来，真正难的是状态设计。有些题的“当前状态”不只是坐标，比如带钥匙的迷宫：你走到同一个格子，手里有没有钥匙，后续能不能开某扇门完全不一样。这时vis数组就要多一维：vis[x][y][key]。钥匙可能是多把，那就要考虑用状态压缩，用二进制位表示当前拥有哪些钥匙，这样一个int就能存下几十种状态组合。
再看倒水问题，两个桶，容量分别是a和b，问倒出c升水的最少操作次数。这个题的“状态”是两个桶当前的水量，每次操作生成新的状态，BFS在状态图上找目标。这类题在机试里叫隐式图搜索，图上没有显式的边，靠转换规则生成邻居。你很容易看出来，如果只把“坐标”理解为二维网格里的点，这类题就完全没法套模板。
我的建议是：每道BFS题动笔之前，先问自己一句话——当前有哪些信息会影响后续决策？这些信息合在一起，就是这个问题的“状态”。把状态表示清楚了，再谈队列和判重。状态表示错，后面全错。
2.4 BFS最容易翻车的三个地方
第一，起点没标记vis，导致后面又把起点放进队列，形成死循环。第二，入队时没有判重，同一个状态被反复入队，MLE/TLE。第三，结构体太大，比如往queue里塞一个vector<int>记录路径，每入队一次就拷贝一次，大数据直接超时。解决办法是路径最后通过记录前驱节点来重建，而不是每个状态都存一份完整路径。
再补充一个多源BFS的例子：有一张地图，多个火源同时扩散，求某个点被点燃的最早时间。做法是把所有火源初始化进队列，步数都是0，然后正常BFS。很多同学只会写单起点，遇到多起点就迷。其实多源BFS只是把初始队列改成塞多个节点而已，思路完全一样。
3. DFS：递归和栈，一边深入一边回溯
3.1 DFS的两种打开方式
DFS和BFS是对应的：一个用显式队列，一个用递归或系统栈。递归写法清晰，适合处理树、棋盘、连通块；手写栈写法稍微啰嗦，但可以避免系统栈溢出，也更容易控制遍历顺序。机试中绝大多数DFS可以用递归写，只有递归深度可能很大时才需要手写栈。
这里要澄清一个误区：DFS不等于递归。递归只是实现DFS最常见的方式，因为系统帮你维护了一个调用栈。如果你愿意，完全可以用stack数据结构手写一个DFS，区别只是栈是显式的还是隐式的。理解这一点对后面处理超大图、避免爆栈很有帮助。
3.2 连通块问题的经典递归
先看一个最常见的DFS应用：统计地图上W组成的连通块数量，八个方向相连也算相连。核心代码是这样的：
int n, m; char mp[MAXN][MAXN]; int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1}; void dfs(int x, int y) { mp[x][y] = '.'; // 标记已访问 for (int i = 0; i < 8; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (mp[nx][ny] == 'W') dfs(nx, ny); } }关键点是：先标记当前格子为已访问，再去递归四个或八个方向。这个“先标记再递归”的顺序极其重要。如果先递归再标记，同一个格子可能被重复递归到，直接栈溢出。我见过无数人写DFS死循环，十有八九就是忘了这一点。
3.3 状态还原：DFS的灵魂
不是所有DFS都需要恢复现场。比如上面连通块染色，本来就是“去过就别再去了”，不需要撤销。但排列、组合、八皇后这类问题，每一条分支都共享同一个数组，你需要在下一次尝试前恢复数组的初始状态，否则上一次分支的选择会污染下一次分支。
举一个标准回溯框架的例子：输出1到n的所有全排列。
#include <iostream> #include <vector> using namespace std; vector<int> path; bool used[10]; void dfs(int pos, int n) { if (pos == n) { for (int v : path) cout << v << " "; cout << endl; return; } for (int i = 1; i <= n; i++) { if (used[i]) continue; used[i] = true; path.push_back(i); dfs(pos + 1, n); path.pop_back(); // 撤销选择 used[i] = false; // 恢复现场 } } int main() { dfs(0, 3); return 0; }这个“做选择 -> 递归 -> 撤销选择”的框架是回溯的骨架。我一开始经常漏掉最后两步，结果生成的排列总是少几个，或者path数组越来越长。后来养成的习惯是，见到“尝试一条路再回来”的描述，先写撤销，再写递归。恢复现场这东西，代码上看起来只是两行，丢了就是整道题崩溃。
3.4 递归深度与栈溢出
DFS的隐藏风险是递归深度。机试里如果一道题明确说要遍历一张大图，递归深度可能到几千甚至几万层，系统栈扛不住。这时候可以手写stack来模拟：把初始状态压栈，循环里取栈顶、扩展邻居、压栈。这个方法不复杂，但很多人平时练得少。
我自己的建议是：先把递归版本写对，再想想如果递归深度可能大到1e5，怎么改成非递归。至少要知道改动的大方向，不然考场上遇到就是两眼发黑。很多在线评测系统对递归深度是有限制的，平时自己写题没爆栈不代表考场不爆栈。
4. 回溯与剪枝：暴力搜索也有方法论
4.1 回溯就是“尝试-撤销-再尝试”
回溯是DFS的一种特殊形式，主要用于“枚举所有合法方案”的题。它的核心思想是：当前选择可能通向正确答案，也可能是一条死路。先假设它正确，继续往下走；走到头发现不行，就退回来试另一种可能。这种“退回来”的操作就是回溯。
上文的全排列代码就是一个典型。这个模板适用面很广：全排列、子集、组合、棋盘问题，都可以往里套。核心是path存当前方案，used标记哪些元素已经用过，pos表示已经选了多少个。你甚至可以把这个问题看成填坑游戏，每个位置都有若干个候选，填完一个就递归到下一个坑位。
4.2 三个常用的剪枝方向
先说可行性剪枝。八皇后中放皇后之前，检查当前位置所在列是否已有皇后、两条对角线是否已有皇后，如果不满足就直接跳过，不需要递归下去。这个剪枝能大幅减少递归次数。相比完全裸搜，复杂度下降非常明显。
然后是最优性剪枝，常见于“求最小步数/最小花费”的问题。方法是维护一个全局最优答案ans，一旦当前路径的代价已经大于等于ans，立刻返回。注意这类剪枝只有在搜索过程中能够获得“当前代价”时才有效，所以很多回溯题都会在参数里带上一个cost或step。
最后是搜索顺序剪枝。数独里最经典的启发式是MRV：每次选择可选数字最少的空格进行尝试，也就是“先填最确定的格子”。这样能让搜索树一开始就变小，后面需要回溯的情况大幅度减少。这个剪枝正确性完全不受影响，只是改变了尝试顺序，但收益非常直观。
4.3 剪枝的正确性检查
剪枝是把双刃剑。剪多了漏解，剪少了等于没剪。我的检查标准是：每写一个剪枝，都要在心里回答“这个分支为什么不可能产生正确答案”。如果只是感觉“不太可能有”，那不能剪。
比如八皇后里检查“当前列是否已有皇后”是正确剪枝，因为它可以证明该分支绝对非法。但“当前行大于两行就返回”就是错误剪枝，因为正确答案可能就出现在更深的分支里。机试里时间再紧，也要保证正确性优先。宁可多算一会儿，也不能交上去WA。
4.4 一道题的剪枝收益
我自己写过一个数独题，不带任何剪枝可以跑好几秒，加上“候选数最少优先”后毫秒级完成。这个收益非常明显，因为剪枝把搜索树的规模从指数级降到了接近“人工填数”的规模。所以遇到搜索超时，先不要急着优化常数，优先看能不能让搜索树变小。
这里顺带提一个思路：很多回溯题都可以用位运算来加速判断。比如八皇后用三个整型分别记录列、主对角线、副对角线的占用情况，判断某个位置能不能放皇后只需要几次位运算。位运算不只是常数优化，有时能把一个判重从O(n)降到O(1)，配合剪枝威力很大。
5. 第七章排坑心得：从TLE到WA的常见死法
5.1 超时：重复状态和无效分支
BFS超时最常见是没有判重或者判重维度不够。二维地图问题只按坐标判重，忽略了“方向”这一维，就会导致同一个点在不同朝向时被反复访问。比如某些题要求机器人转向也算一步，那么状态里必然包含方向，vis[x][y][dir]才是完整的判重。
DFS超时最常见是剪枝不足。可以先跑一次小数据，看看递归次数是多少，估算一下大数据能不能扛住，不能就继续剪。机试的时间限制一般不会特别宽裕，搜索题裸搜大概率过不了，所以剪枝不是一个“优雅加分项”，而是必需品。
注意：TLE的优化顺序永远应该是优先减少搜索树规模，再优化常数。很多人一上来就想着把
queue换成数组模拟，或者把cout改成printf，结果作用不大。正确的思路是先想清楚哪些分支是无效的、哪些状态是冗余的。
5.2 内存爆炸：队列里的结构体太大
有位同学写BFS时在结构体里塞了一个vector<int>用来记录路径，数据一大直接MLE。实际上路径可以通过记录前驱节点来重建，不需要每个状态都存一份完整路径。这个坑非常典型：看起来代码简单，但空间复杂度被结构体拷贝彻底带崩了。
更隐蔽的MLE出现在状态压缩上。有些题的vis数组要用到三维甚至四维，如果每维都是100，直接开数组可能就内存超限了。这时候要么压缩维度，要么改用按需存储的哈希表。机试里最简单的做法是先把能压缩的信息压成int，比如把坐标(x, y)压成x * m + y，既方便存vis，也方便放进队列。
5.3 答案错误：边界和恢复现场
WA的原因比超时更隐蔽。常见的有：起点和终点重合时忘记输出0；BFS里把终点直接continue掉了；DFS恢复现场后没有把当前格子的“已访问”标记也恢复。八皇后里对角线的坐标差算错，导致互相攻击的皇后没被拦住，这种问题只有细致排查才能发现。
我调得最久的一次是某个回溯题，恢复现场时只恢复了used数组，忘了恢复答案数组中的值，导致一组数据总是多几个元素。后来我把每次递归入口的状态都打印出来，才发现是撤销少写了一行。建议调试时把小数据手推一遍，把递归输出和手算结果对一遍，很快能定位。
5.4 快速定位问题的方法
遇到搜索题出错，我一般按这个顺序排查：
- 先看判重有没有漏，维度是否完整；
- 再看边界和初始化，起点终点是否特判；
- 然后看状态恢复，撤销操作是否齐全；
- 最后打印路径，观察每一步是否符合预期。
其中打印路径是最好用的手段。你可以在关键递归入口输出当前状态，跑一组小数据，看到底哪一步开始不对劲。这一招比反复看代码有效得多。很多WA问题本质上就是某个状态被污染了，你把状态流打出来，污染点马上现出原形。
6. 读完后我给自己定的刷题计划
6.1 从最简单的题开始
我给自己安排的顺序是：先做纯BFS迷宫，再做纯DFS连通块，然后做全排列和八皇后。这几类题可以一天内各刷一道，关键是总结模板。同一个模板写三遍以上，肌肉记忆就有了。不要贪多，先保证简单题不WA。
很多人会跳过简单题直接挑战难题，结果掉进调试地狱。搜索题的信心是靠简单题堆起来的，当你闭着眼睛都能写出BFS的队列循环，你才有余力去想状态压缩和剪枝启发式。
6.2 刻意练习状态设计
第二步是练状态设计：三维BFS，比如拿到钥匙后的地图；多源BFS，比如多个起点同时扩散；隐式图BFS，比如倒水、单词接龙。这类题的价值在于迫使你想清楚“什么是状态”，想清楚了代码反而不是问题。
这阶段我还会刻意练习状态压缩。一张地图最多十几个可交互物体，用二进制位表示是否为已获得状态，一个int就能放下。这类写法写熟了，很多看起来状态爆炸的题都能用BFS跑出结果。
6.3 把模板变成自己的
不要直接背书里的代码。我每次学一个模板，都会尝试改两处：变量命名、循环方向、判重矩阵的存储方式。改完再跑一遍原题，确认没改坏。这个过程能让你真正理解模板里每一行在干什么，而不是成为打字机。
比如BFS的四个方向，有人喜欢用数组加循环，有人喜欢单独写四个if。两种写法都能AC，但你必须知道为什么能AC。把模板改成自己习惯的风格之后，考场上写出来的就是本能反应，而不是回忆课本。
6.4 这一章对后续章节的意义
读完第七章再往下翻，图论里的最短路、拓扑排序，动态规划里的记忆化搜索，本质上都是搜索思路的延伸。BFS理解到位了，Dijkstra就容易懂；DFS理解到位了，二叉树遍历和图遍历就顺了。这也是为什么第七章放在数据结构之后、图论之前，它是一座桥。
我个人读完这章最大的体会是：搜索题的难点从来不在“会背模板”，而在于“知道把一个具体问题翻译成状态和转移”。这个能力只能靠刷题和复盘慢慢养，没有捷径。如果你现在也卡在第七章，不必慌，把BFS的队列和DFS的栈当作两个老朋友，多写几道题，你会发现搜索其实是机试里最踏实的一类题——因为它不需要猜，只要把状态空间遍历完，答案就在那里。
模板背得再好，不如自己debug半小时来得深刻。第七章刷完，我的信心反而比看书前更足，因为搜索至少让人看到了一条清晰的努力路径：状态想清楚，暴力写对，剪枝跟上，剩下的交给机器。
