考研机试的备考里《王道论坛计算机考研机试指南》前四章我翻得还算顺利排序、数据结构、数学问题都算有章可循。但到了第五章搜索我的节奏明显慢了下来原因是这一章和前面的思维方式完全不同它不讲某个固定算法而是教你怎么把“所有可能”找出来再从可能里筛出答案。这一章覆盖枚举、递归、DFS、BFS、剪枝机试里的压轴题大部分都是从这里出的。很多院校的上机题基础题是排序模拟拉开差距的往往就是一道搜索题。文章是我结合二刷第五章的笔记和实际刷题经历整理的适合正在准备机试、尤其是第一次接触搜索的同学参考。1. 先把第五章的骨架摸清楚1.1 这一章到底在讲什么第五章的核心就一句话在状态空间里找答案。所谓状态空间可以理解成所有可能情况的集合。比如迷宫里每一步走到哪个格子这是一个状态从起点到终点的一条完整路线是状态空间里的一个元素N皇后棋盘上的一种摆法也是一个状态。搜索要做的事就是把这些状态有顺序地遍历一遍找到符合条件的那一个或最优的那一个。书里把搜索拆成了几个层次。最底层是枚举直接循环遍历所有可能然后是用递归实现的深度优先搜索一条路走到底、走不通再回头接着是用队列实现的广度优先搜索一层一层往外扩最后是剪枝在遍历过程中提前砍掉明显不行的分支把时间从“跑不完”降到“跑得动”。这个结构安排得很合理。枚举是“无脑但有边界”的遍历DFS和BFS才引入“顺序”的概念剪枝是在你已经有完整搜索能力之后才谈的优化。刚上手时如果先去抠剪枝很容易被绕晕因为剪枝的所有前提都是你能把搜索完整写出来。1.2 我为什么建议按“枚举 → DFS → BFS → 剪枝”这个顺序学这个顺序我是踩过坑之后才认可的。第一次看第五章我急着做DFS题结果卡在递归上连状态恢复都理解不了更别说写对回溯。后来回头老老实实把枚举过了一遍把“三种循环嵌套把情况列全”这件事练透再去看DFS才反应过来DFS不过是用递归实现的一种更灵活的枚举只是它的“循环”通过递归调用栈来维护不用手动写那么多层for。依赖关系大致是这样枚举帮助你建立“所有可能情况”的直觉递归是DFS的地基理解调用栈才能理解回溯DFS是理解剪枝的前提不知道完整搜索什么样就没法谈优化BFS用到队列和“层”的概念和DFS形成互补最短步数问题它是最优解。所以我的建议是先别跳着刷按照书中顺序一题一题过尤其是枚举基础不够扎实的话后面会很吃力。1.3 开始刷题前的自测清单动笔之前可以自测三件事不用全懂只要有基础就行循环嵌套能不能熟练写出两层、三层for循环并控制上下界不越界STL基础会不会用stack、queue、vector知道push、pop、top、front这些操作的区别复杂度直觉知不知道1秒内大概能跑多少次普通循环以及为什么千万级和亿级有时差别很大我的判断标准是能独立写一个递归求阶乘能用一个队列跑通简单的队列输出就可以开始本章。如果连递归return是怎么回事都还要想半天建议先花半小时把递归函数练熟否则DFS部分会很痛苦。这一章不适合零基础硬啃但也不需要你懂什么高级数据结构门槛其实不高。2. 枚举把“暴力”写得不那么难看2.1 枚举题的本质先把所有可能性摆出来枚举是搜索算法的雏形也是机试里最常用来垫底的基础题。它不讲究什么巧妙的优化核心就两条情况列全、判断正确。做题时首先要确定“枚举什么”。有的题是区间枚举比如给定整数区间找出所有满足某性质的数这种直接for循环遍历区间每个数就行。有的题是多变量枚举比如百钱买百鸡问题要枚举鸡翁、鸡母、鸡雏的数量再用钱数和只数两个条件过滤。多变量枚举的关键是给每个变量划出合理范围范围太大浪费时间范围太小会漏解。我常和同学说枚举题本身不难但它考察的是你“把问题转化为代码”的能力。一个枚举题的正确做法不是急着写代码而是先在纸上把变量和取值范围写清楚再考虑哪些条件可以提前用掉减少循环层数。这一步做好代码自然就顺了。2.2 三个容易踩的坑枚举看上去简单但机试现场翻车的概率一点都不低。我开始刷题时至少踩过下面这几个坑。第一个是边界条件。找水仙花数这种三位数区间题循环范围应该是100到999有人写成0到999多跑了无所谓的部分更常见的是该写小于等于的地方写成了小于导致最后一个数漏掉。我建议凡是涉及区间上下界的循环写完立刻检查三处——起始值、终值、等号。第二个是重复枚举。多变量组合题里如果两个变量可以互换必须人为规定顺序。比如从n个数里取两个数如果写成“for i 从0到nfor j 从0到n”每个组合会被记录两次。解决办法是让j从i1开始循环保证组合只出现一次。第三个是输出顺序。很多判题机对输出顺序有严格要求要求字典序就必须让循环变量从小到大枚举并且在循环嵌套里先枚举靠前的变量。别小看这个问题我见过有人逻辑完全正确只是因为输出顺序反了直接WA到怀疑人生。2.3 性能优化的意识提前退出与缩小范围枚举题虽然“暴力”但代码层面还是有优化空间。最实用的一条是判断条件尽量往早期放。三层循环里如果某种条件在内层就能判断就不要放到最外层之后再判断。把最内层的无效循环省掉效率提升非常明显。第二是缩小枚举范围。比如枚举素数因子只需要判断到sqrt(n)不需要到n判断年份合法性先把月份对应的天数存成数组再根据闰年修正。这些细节不改变复杂度量级但能把常数时间降低有时就决定了极限数据会不会超时。还有一种更激进的思路是预计算。如果题目的输入范围有限比如最多几千组查询可以先把所有可能答案提前算出来存到数组里查询时直接O(1)返回。这种“空间换时间”的思路在机试里很实用第五章后面一些搜索题也会用到类似思维到这里可以先培养意识。我刷枚举专题时给自己定了一个习惯每道题写完后把循环次数估算出来。如果最坏情况可能在千万级以上就想想能不能提前结束或缩小范围。这个习惯在之后写搜索剪枝时会非常有用。3. DFS递归就是一棵隐形的树3.1 从递归讲起DFS到底是什么DFS全称是深度优先搜索核心思想不复杂从一个起点出发沿着一条路走到黑走不通了再退回上一个岔路口换一条路继续。它背后的数据结构是系统维护的调用栈递归每深入一层就相当于在栈里压入一个状态return一层就弹出一个状态。看书时我一度被困在“递归怎么想清楚”这个问题上。后来一个学长给了个比喻一下点透我**把DFS想象成一棵树根节点是初始状态每个分支是一种选择叶子节点是没有路可走或到达终点的状态。递归函数做的事就是不断向下扩展分支直到叶子再返回。**你不需要一次性想象整棵树只需要想清楚当前节点该做什么、怎么走到下一层、什么时候返回。DFS应用最典型的是排列组合、N皇后、数独以及图中连通块统计等问题。它的代码模板其实非常固定用熟了之后会发现大部分DFS题都是同一套骨架。void dfs(当前状态) { // 1. 判断是否到达目标或非法状态 if (满足终止条件) { 记录结果或更新答案; return; } // 2. 遍历所有可能的选择 for (每个可选分支) { 修改状态; dfs(新状态); 恢复状态; // 回溯时恢复现场 } }关键在于“修改状态”和“恢复状态”必须成对出现这是DFS能遍历完整棵搜索树的保证。3.2 回溯与状态恢复最容易WA的地方回溯是DFS的精髓也是新手最容易出错的地方。所谓回溯就是在递归返回上一层时把对状态的修改还原让上一层可以继续尝试其他分支。举个最简单的例子生成1到n的所有全排列。如果用数组path记录当前排列用bool数组used记录某个数字是否被用过那么递归进入下一层之前要把used[i]设为true记得把对应数字放进path递归返回之后必须再把used[i]设回false否则同一个数字在另一个分支里会被误判为“已用过”。void dfs(int depth, vectorbool used, vectorint path, int n) { if (depth n) { for (int x : path) printf(%d , x); printf(\n); return; } for (int i 1; i n; i) { if (used[i]) continue; used[i] true; path.push_back(i); dfs(depth 1, used, path, n); path.pop_back(); used[i] false; } }这段代码里used[i] true和used[i] false就是一对“修改-恢复”。忘了恢复会导致某些排列生成不出来或者生成出重复结果最后答案完全错乱。我在刷题时曾经为了一行没写路径恢复白白排查了半小时。调试这类问题有个笨但有效的办法在递归函数入口用printf打印当前深度和状态肉眼就能看出某个分支的状态是不是被污染了。等代码稳定了再把printf删掉。3.3 递归出口与参数设计想清楚再写就快了DFS出错的另一个常见点在于递归出口。递归必须有明确的终止条件否则会无限循环直到栈溢出。具体来说出口要回答两个问题什么时候算成功什么时候算失败。比如判断棋盘上是否能走到某个位置成功是坐标等于目标失败是越界或撞墙。出口写对了DFS的骨架才算稳。参数设计也是新手容易纠结的地方。我的经验是分三种情况如果状态是基本类型且需要在递归中不断变化的直接用值传递省心但可能有拷贝开销如果是数组或复杂状态用引用传递或全局变量但修改后必须手动恢复如果需要记录完整路径可以用一个stack或vector配合递归同步维护。对大多数机试题用全局数组加引用传参就可以关键是每一层的修改都配好恢复。这个经验是在N皇后题上建立的。一开始我把棋盘矩阵整个拷来拷去代码冗余不说还超时后来改成全局数组加恢复标记清爽很多。3.4 机试现场我遇到过的DFS坑DFS相关的坑不只逻辑问题还有一些现场才能感受到的细节。第一个是爆栈。递归深度如果达到几万层系统栈可能直接被压爆程序运行时会直接崩溃或返回段错误。我们常用的在线判题环境递归深度通常不建议超过上万层。如果题目搜索空间非常深比如求所有可能的子集可能要考虑把递归改成显式栈实现或者换BFS思路。第二个是死循环。在一些图或状态转移类DFS题里如果状态会循环转移且没有标记“已访问”程序就会在几个状态之间来回跳。解决办法是加visited数组在进入新状态时检查。第三个是超时。DFS在没有剪枝的情况下会遍历所有状态状态多时很容易跑几十秒。我遇到过一道题暴力DFS在本地跑小样例完全正常一提交就超时原因是没有剪枝。这也是为什么第五章后半部分专门讲剪枝它几乎决定了搜索题能不能过。4. BFS最短步数问题的标准答案4.1 BFS为什么能保证最短步数BFS和DFS最大的区别在于遍历顺序。DFS是纵着走BFS是横着扩先把起点周边一圈走完再走第二圈一层一层向外扩展。这种“层序遍历”的特征决定了如果每条边的代价相同第一次到达目标状态时的路径一定是最短的。生活里类似场景是“以自己为圆心画圈找人”第一步找朋友第二步找朋友的朋友第三步找朋友的朋友的朋友。第一次找到目标那一步就是最少介绍次数。机试里最经典的是迷宫最短路每一步上下左右移动代价都是1BFS天然能算出最少步数。DFS虽然也能找出一条可行路径但不保证最短这是最本质的差别。所以见到“最少步数”“最短路径”这类字眼优先考虑BFS。4.2 一个可以直接套的BFS模板BFS的模板比DFS还固定核心部件是队列、距离数组、方向数组。以迷宫为例代码大致是这样#include queue #include cstring using namespace std; const int N 105; int n, m; char maze[N][N]; int dist[N][N]; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; int bfs(int sx, int sy, int tx, int ty) { memset(dist, -1, sizeof(dist)); queuepairint, int q; dist[sx][sy] 0; q.push({sx, sy}); while (!q.empty()) { auto cur q.front(); q.pop(); int x cur.first, y cur.second; if (x tx y ty) return dist[x][y]; for (int i 0; i 4; i) { int nx x dx[i], ny y dy[i]; if (nx 0 || nx n || ny 0 || ny m) continue; if (maze[nx][ny] #) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } return -1; }这段代码里有几个关键点dist[nx][ny]既是距离记录又充当vis数组初始化为-1表示未访问省掉了一个数组终点判断放在出队时代码好理解实际也够用方向数组dx、dy按顺序写四个方向都不会遗漏。建议初学先按这个模板写跑通几道题之后再考虑优化终点判断的位置。4.3 状态去重与编码队列里到底该存什么BFS的速度很大程度上取决于状态量而状态量由去重决定。迷宫题里状态就是坐标用二维dist足够。但有些题目状态不止一个坐标比如要同时移动两个箱子或者需要记录方向朝向这时就要考虑“状态怎么表示才能放进队列、怎么去重”。我遇到过一道题主角在迷宫里可以移动还需要记录当前朝向结果我一开始只用坐标做判断导致不同朝向的同一位置被错误地当成同一状态答案差了好远。后来把状态定义成“坐标朝向”的结构体再用三维数组标记才算通过。状态比较复杂时有几种常见的编码方式用结构体定义状态存入队列用一维数组加哈希比如把坐标或方向拼成一个整数作为标记索引用unordered_set直接存编码后的状态。状态设计是搜索题里最考验功力的部分也是刷题经验积累最快的地方。看懂一道BFS题最重要的是想明白“这个题的状态变量到底是什么”。4.4 BFS常见的几个低级错误BFS代码不长但五花八门的错误我能列出一堆起点没标记dist[sx][sy]忘了初始化为0起点会被重复入队导致步数膨胀或死循环队列没有pop取出队首后忘了弹出队列永远不为空程序跑到地老天荒越界判断顺序写反先访问数组再判断越界直接段错误多组输入没有清空数组dist残留上一组数据导致新一组用例答案错误步数更新写错dist[nx][ny]写成dist[x][y]1却写成dist[cur]之类逻辑完全对不上。其中最阴的是多组输入的坑。很多题会连续给多组迷宫数据初始化一定要放在每组数据读取之后、BFS之前。我第一次刷BFS时为了省事只在程序开头memset了一次结果第二组数据永远答案不对排查了特别久才发现问题。5. 剪枝从“能跑”到“跑得动”5.1 什么时候才需要剪枝如果一道搜索题数据范围很小比如N8的全排列直接DFS暴力就能过根本不需要剪枝。但机试里的搜索题往往数据范围卡得很紧比如N25的排列或大棋盘上的搜索暴力递归会在几秒内把判题机跑超时。判断是否要剪枝最直接的办法是估算状态数。假设每一步有k种选择递归深度为d状态数大约是k^d。当这个数量达到10^9以上时普通递归肯定跑不过1秒需要思考如何减少分支或提前终止。我刷题时会养成一个习惯先写一个最朴素的搜索版本用题目给的最大数据本地跑一遍观察耗时。如果超过1秒再考虑剪枝。这样做有个好处剪枝逻辑出现问题时可以拿朴素版本的小数据结果来对比验证正确性。5.2 三类常用的剪枝策略剪枝的方式很多但机试阶段掌握下面几类就够用。可行性剪枝是最常用的如果当前状态已经不可能到达合法答案直接return。比如数独填数时某个数字在当前行、列、宫都已经出现过就不往下递归比如DFS走迷宫前一步已经把目标围住了后面所有分支都没意义。最优性剪枝适用于求最优解的题目维护一个当前最优答案如果递归到某层时已有的代价加上至少还要花费的代价已经不小于当前最优值就剪掉。最典型的是求最短路径时当前步数已经大于等于已知最少步数直接返回因为后面不可能更优。奇偶性剪枝是DFS迷宫题里的经典技巧在一个只能上下左右移动的棋盘上从起点到终点的最短步数奇偶性一定和两点横纵坐标之差的绝对值之和的奇偶性相同。如果剩余时间或剩余可走步数的奇偶性不符合直接剪掉能减少大量无效分支。还有一种很实用但容易被忽略的“顺序剪枝”调整搜索分支的遍历顺序让大概率正确的分支先被搜到。比如拼木棒题先尝试较长的木棒能更快找到可行解而较短的木棒放在后面尝试减少因为分支顺序导致的大量回溯。这个不算严格剪枝但对跑时间优化帮助很大。5.3 剪枝的边界别把正确答案剪掉剪枝的本质是“用逻辑判断提前停止搜索”所以剪枝条件的正确性必须严格证明。一个不严谨的剪枝可能让本来有解的题目返回无解这是搜索题里最头疼的隐性Bug。我踩过最惨的一次是在一道拼木棒题里加了一条自认为很合理的剪枝如果当前组合长度已经超过目标长度就返回。逻辑上没毛病但实现时漏掉了一种情况——某根木棒长度大于目标时问题本身已经无解应该提前排除而不是在递归里靠超长判断去剪。结果小样例能过大样例莫名WA了很久。我给自己的底线是不确定的剪枝一律不加。WA比TLE更打击心态TLE还能通过优化代码抢救WA要大海捞针找逻辑漏洞。加剪枝时每次只加一条立刻用组对比测试验证确认新剪枝不会改变结果后再加下一条。这个流程慢一点但安全。6. 刷题过程中的常见问题与调试技巧6.1 错误类型速查表刷完第五章节我整理了一张排查表每次报错先按表自查效率提升明显错误类型常见原因排查思路段错误/崩溃数组越界、递归爆栈、空指针检查所有数组下标是否越界尤其是边界判断顺序运行超时复杂度太高、缺剪枝、死循环估算状态数本地用大数据测试耗时答案错误逻辑缺陷、状态恢复遗漏、输出格式构造小样例手算或用朴素版对拍内存超限队列或数组存储太多重复状态检查vis是否正确标记减少队列中的冗余状态有了这张表遇到问题先判断错误类型再针对性排查比漫无目的地改代码快很多。6.2 现场调试三板斧机试现场没有IDE里那么方便的断点调试我用的是三板斧。第一板斧是printf调试。在递归入口打印当前状态在BFS出队时打印坐标和步数。虽然土但对搜索题特别有效能直观看到状态是否按预期扩展、回溯是否正确。打印输出记得最后删掉不然会影响判题。第二板斧是小数据手算验证。样例能过的时候别急着交先构造一个更小的数据比如3x3迷宫、n1的全排列自己手算出答案再用程序跑一遍确认一致。第三板斧是边界样例私测。搜索题最常见的WA原因是边界没处理好我会刻意测1行1列迷宫、目标不可达、空图、最大规模数据等场景。尤其是最大数据能在本地跑出耗时提前判断会不会TLE。6.3 我的刷题节奏与分类记录法第五章题量不小我的刷法是分三轮推进。第一轮按章节顺序把所有例题和课后题过一遍目标是理解每个模板第二轮只刷之前做错的题不看题解强迫自己独立写出完整代码第三轮混入其他章节的搜索题打乱顺序模拟考场。做题时我会给每道题打三个标签题型枚举/DFS/BFS/剪枝、状态定义、踩坑点。比如某道题的状态是“位置已收集物品集合”我会单独记录状态设计过程这对积累搜索题经验非常关键。还有一个心态想分享搜索题做不出来很正常卡住时不要急着看题解先把问题分解成三段——状态是什么、每一步有哪些选择、目标是什么。这三个问题想清楚代码基本就有了。我遇到过很多次“感觉不会写但把状态定义写出来后代码顺理成章就出来了”的情况。第五章节刷完后面学图论、动态规划都会顺畅不少因为搜索本身就是很多高级算法的基础。如果说机试是一座山搜索就是半山腰的必经之路这一章花的时间完全值得。