拿到这本《王道论坛计算机考研机试指南》的时候我已经把前六章的题刷得七七八八。真正让我卡住的是第七章。这一章讲的是搜索——BFS、DFS、回溯、剪枝听起来都是课本上很基础的名词但机试里真正拉开差距的恰恰是把这些基础玩出花来的能力。如果你也正在准备计算机考研的复试上机或者刚接触在线评测系统希望能用最短的时间搞懂搜索这篇笔记就是按我实际读第七章的顺序整理的。第七章不是让你背三个模板就完事它是让你从“暴力想不到”变成“暴力也有章法”。1. 第七章的定位为什么机试必须啃下搜索1.1 从目录看这一章的野心原书第七章的标题是“搜索”。我当时心里是有点意外的搜索不是数据结构里的内容吗怎么单独占一整章后来刷题才明白机试中的搜索不是一个孤立的算法而是一整套思维方法怎么描述状态、怎么扩展状态、怎么从“所有可能”里挑出有效路径。这一章反复强调四件事状态、判重、剪枝、恢复现场。这四个词几乎能覆盖机试里大部分搜索题。一开始我看目录觉得内容不多BFS一节、DFS一节、回溯和剪枝再各一节好像很好搞定。真正做题才发现每一节背后都是十几个变形。比如BFS可以用于迷宫最短路径也可以用于隐式图搜索比如倒水问题DFS可以用于连通块计数也可以用于全排列、八皇后、数独。第七章表面在讲几个模板实际是在训练你一种“翻译能力”把题目描述翻译成状态空间里的节点和边。1.2 搜索题在机试里的出场姿势搜索题在机试中出现的频率非常高经常是整套卷子里第二、第三题的位置。常见的场景有迷宫里找最短路径、地图上数连通块、给你几个数做全排列、八皇后、数独、倒水问题、单词接龙。这类题看起来千差万别但本质都是一个东西在一个有向的状态空间里找目标。很多同学包括我一开始觉得搜索就是暴力把每种情况都走一遍。这句话没错但机试的难点从来不在于“知道该暴力”而在于“怎么暴力得又快又不挂”。暴力裸搜大概率超时怎么减少无效分支状态太多怎么存这就是第七章真正要解决的问题。所以它放在数据结构之后、图论之前是因为搜索要用到队列、栈、树这些基础结构同时又是后面最短路径、记忆化搜索这些内容的思想基石。1.3 我的阅读路线我第一遍只看了BFS和DFS因为这两块模板性最强看完就能上手写题。第二遍再回过头啃回溯和剪枝这部分更需要做题来建立手感。我建议第一遍阅读时不要急着过完所有小节先把BFS模板抄下来找两三道迷宫题跑通再继续往下走。搜索这个东西看十遍不如自己调一遍bug。这一章的章节顺序安排是合理的但我不建议完全照顺序读。你可以按“模板先行 变体练习”的思路来先掌握BFS和DFS的基本写法再用后面的回溯和剪枝去处理变体题。这样不容易晕也不会出现“书看懂了、题还是不会”的尴尬。2. BFS先见先出把层数当成路径长度2.1 一句话理解BFSBFS用队列维护“当前层”的所有节点每次从队首取出一个节点把它能到达的下一层节点从尾部入队。因为先进先出所以同一层的节点一定比下一层先被访问。第一次访问到某个节点时的步数就是从起点到这个节点的最短步数。这是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)); queueNode 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里塞一个vectorint记录路径每入队一次就拷贝一次大数据直接超时。解决办法是路径最后通过记录前驱节点来重建而不是每个状态都存一份完整路径。再补充一个多源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; vectorint 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时在结构体里塞了一个vectorint用来记录路径数据一大直接MLE。实际上路径可以通过记录前驱节点来重建不需要每个状态都存一份完整路径。这个坑非常典型看起来代码简单但空间复杂度被结构体拷贝彻底带崩了。更隐蔽的MLE出现在状态压缩上。有些题的vis数组要用到三维甚至四维如果每维都是100直接开数组可能就内存超限了。这时候要么压缩维度要么改用按需存储的哈希表。机试里最简单的做法是先把能压缩的信息压成int比如把坐标(x, y)压成x * m y既方便存vis也方便放进队列。5.3 答案错误边界和恢复现场WA的原因比超时更隐蔽。常见的有起点和终点重合时忘记输出0BFS里把终点直接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半小时来得深刻。第七章刷完我的信心反而比看书前更足因为搜索至少让人看到了一条清晰的努力路径状态想清楚暴力写对剪枝跟上剩下的交给机器。