1. 从“暴力枚举”到“智能搜索”蓝桥杯搜索专题的本质如果你参加过蓝桥杯或者刷过它的历年真题大概率会有一个感觉这比赛怎么这么爱考“搜索”从最基础的迷宫问题到复杂的状态空间枚举搜索算法几乎贯穿了从省赛到国赛的各个难度层级。很多同学刚开始接触时会把搜索简单理解为DFS深度优先搜索和BFS广度优先搜索的代码模板背诵但一到真题实战面对稍微复杂一点的约束条件或者状态表示就立刻无从下手感觉背的模板完全用不上。这其实是对“搜索”的误解。蓝桥杯尤其是软件类竞赛考察的搜索远不止是两个遍历算法。它的核心是“在庞大的、隐式的解空间树或状态图中高效地、有策略地找到符合题目要求的解或最优解”的能力。DFS和BFS只是两种最基本的“遍历”策略相当于给了你一把铲子DFS和一个探照灯BFS告诉你如何系统地“翻遍”每一个角落。但真题真正考验你的是你知不知道要挖哪座山山有多大怎么挖才能不白费力气以及在挖的过程中如何识别死路并提前回头我参加过也辅导过不少蓝桥杯看过太多同学在搜索题上折戟。常见的痛点包括一看到题就想套模板结果状态定义错误递归参数传得一塌糊涂不会估算时间复杂度写出来的程序在小数据上跑得飞快一提交就超时对“剪枝”只有模糊的概念不知道具体从哪里下手剪了跟没剪一样。这篇总结我就结合几道经典的、有代表性的蓝桥杯真题来拆解搜索专题的实战心法。我们不只讲DFS和BFS怎么实现更要讲清楚为什么这道题用DFS而不用BFS状态如何设计才能方便搜索和判重有哪些常见的、一用就灵的优化剪枝技巧目标是让你下次再遇到搜索题时能有一套清晰的思考路径而不是慌乱地回忆模板。2. 搜索算法的“武器库”DFS与BFS的适用场景辨析在深入真题前我们必须把两件核心武器的特性和适用场景彻底厘清。这不是死记硬背而是理解其底层逻辑才能做出正确选择。2.1 深度优先搜索一条路走到黑适合枚举所有“方案”DFS的核心思想是“递归”与“回溯”。它尝试一条路径走到尽头如果发现是死路就退回上一个岔路口选择另一条路。这种特性使其非常适合解决**需要枚举所有可能“方案”或“排列”**的问题。典型特征与适用场景问题形式求所有满足条件的方案、路径、排列组合。例如“输出所有可能的...”、“计算总共有多少种方法...”。状态空间通常可以建模为一棵“解空间树”。树的每一层代表一次选择分支代表不同的选项。目标遍历整棵树收集所有叶子节点合法解。蓝桥杯常见题型全排列问题、N皇后问题、数独求解、部分和问题、图的连通块计数等。一个关键的心得DFS实现时最重要的就是设计好“状态”。这个状态包括了当前递归层的所有必要信息通常通过函数的参数传递。例如在走迷宫时状态是当前坐标(x, y)在全排列时状态是当前已经确定了前几位数字的排列结果、以及哪些数字已被使用过的标记数组。设计得好的状态能让递归函数逻辑清晰剪枝方便。2.2 广度优先搜索层层推进适合寻找“最短”或“最少步数”BFS的核心思想是“队列”与“层次遍历”。它从起点开始先访问所有距离为1的点再访问距离为2的点以此类推。这种特性使其天然适合求解最短路径、最少操作步数的问题。典型特征与适用场景问题形式求从起点到终点的最短距离、最少变换次数、最快逃离步数。状态空间可以建模为一个“状态图”。图中的节点是一种状态边是一次状态转移一次操作。目标找到从初始状态节点到目标状态节点的最短路径。蓝桥杯常见题型迷宫最短路径、八数码问题华容道、单词接龙的最短转换序列、灌溉问题等。一个关键的心得BFS实现时状态判重是避免死循环和提升效率的重中之重。因为BFS会多次遇到同一状态如果不记录是否访问过队列会无限膨胀。通常使用哈希表如unordered_map/unordered_set或根据状态特点编码成唯一字符串/数字来记录已访问状态。另一个要点是在将子状态加入队列前就进行合法性检查和判重而不是在从队列取出时才做这能有效减少无效的队列操作。2.3 选择决策流程图面对一道新题如何快速决定用DFS还是BFS你可以问自己下面几个问题问题问什么是“所有可能”DFS还是“最短/最少”BFS状态转移的代价是否均为1BFS通常要求每次转移的“代价”相同如走一步。如果代价不同如带权图则需要使用优先队列BFSDijkstra算法。解空间是否可能极深但答案在浅层如果用DFS搜索一个极深的树但答案可能在很浅的地方DFS可能会浪费大量时间在深层无用的分支上。此时BFS更有优势。是否需要记录完整路径DFS回溯天然容易记录路径通过递归栈BFS记录路径需要额外维护每个状态的前驱节点。很多蓝桥杯的难题其实是这两种思想的结合或变体比如迭代加深搜索IDDFS就是融合了DFS的空间优势和BFS能找到最短解的优势。3. 真题拆解一DFS的典型应用与优化艺术我们拿一道非常经典的DFS题目来切入看看如何将思路转化为代码并一步步进行优化。例题蓝桥杯历届试题——“带分数”问题描述100 可以表示为带分数的形式100 3 69258 / 714。还可以表示为100 82 3546 / 197。注意特征带分数中数字1~9分别出现且只出现一次。输入一个正整数N (N1000*1000)输出用数字1~9构成带分数表示N的方法数。第一步问题转化与暴力DFS思路这道题的本质是在数字1~9的全排列中插入两个加号和/将其分割成三个部分整数部分、分子、分母并满足等式N 整数 分子 / 分母且分子必须能被分母整除。 最直接的暴力做法是生成数字1~9的所有全排列共9! 362880种。对于每一种排列枚举两个分割点设整数部分取前i位分数部分取中间j位分母取剩下的位将三段字符转换成整数。检查是否满足N A B / C且B % C 0。这个思路清晰但效率如何对于每个排列我们需要枚举分割点。整数部分最少1位最多7位因为分子和分母至少各1位。粗略估算计算量约为9! * 8 * 8 ≈ 360k * 64 ≈ 2300万次整数转换和判断。对于N最大100万的情况这个计算量在蓝桥杯的时限内通常1秒~2秒是非常危险的在C中可能勉强通过但绝非佳选且在其他语言中极易超时。第二步DFS实现与状态设计我们不需要先生成所有排列再切割。更好的方法是在DFS生成排列的过程中同步进行切割和计算。 我们可以设计DFS函数dfs(pos, a, b, c)其中pos: 当前正在处理数字1~9中的第几个数字0-indexed。a: 当前已经构成的整数部分的值。b: 当前已经构成的分子部分的值。c: 当前已经构成的分母部分的值。但这样参数太多。更巧妙的是我们固定搜索顺序就是生成排列的顺序。在递归过程中我们可以决定当前生成的数字是追加到整数部分、分子部分还是分母部分然而我们还需要知道当前正在构建的是哪一部分。 一个更实用的状态设计是在DFS生成排列的过程中每当生成完一个数字我们就尝试更新当前正在构建的段整数、分子、分母并判断是否可以提前截止剪枝。实际上更清晰的写法是两层DFS外层DFS/循环枚举整数部分A的位数lenA1到7。内层DFS从剩下的数字中枚举分子B的位数lenB1到 9-lenA-1分母C自然获得剩下的数字。核心的DFS函数负责生成指定位数的数字排列。但这样写仍然复杂。竞赛中更常见的优化思路是对排列进行枚举但在枚举过程中利用等式关系进行提前剪枝。第三步关键优化——可行性剪枝暴力枚举所有排列再检查浪费了大量时间在明显不可能的解上。我们可以在构造数字的过程中就进行判断。 设我们正在构造排列当前已经确定了前k个数字。我们可以尝试用前i个数字构成整数部分A1 i k。那么A必须小于N因为B/C是正数。 然后对于剩下的k-i个数字我们继续枚举分子B的结束位置j。此时我们有了A和B可以根据公式推导出C应该满足的条件 由N A B / C得B / C N - A所以C B / (N - A)。 但C必须是一个整数且(N-A)必须大于0。因此我们可以在DFS过程中每当确定了一段A后就检查N - A 0吗剩下的数字能否组成一个整数C使得B (N - A) * C成立并且B恰好由剩下的某些数字构成这个检查可以在递归的较浅层进行如果发现N - A 0那么当前以A开头的所有分支都可以剪掉了因为加上正分数只会更大。这叫做可行性剪枝。更进一步我们甚至可以在确定A后直接计算出B和C应该是什么然后检查剩下的数字是否能恰好组成B和C。这需要更复杂的状态记录。但一个更简单高效的实现方法是使用DFS生成数字1~9的全排列作为一个数组num[]。在每一个排列生成后或在生成过程中用两层循环枚举分割点i和j。但在枚举前先进行一个强力剪枝计算A。如果A N直接break内层循环因为继续增大A更不可能。这个剪枝效果非常显著。因为对于大多数排列开头的A可能很小但也有很多排列A一开始就很大。一旦A N对于固定的排列后续无论怎么分割A只会更大因为i增大整个等式左边必然大于N所以当前排列的后续所有分割方案都无需再试。第四步代码实现要点与实测#include bits/stdc.h using namespace std; int n, ans 0; int num[9] {1,2,3,4,5,6,7,8,9}; // 待排列数组 // 将数组num中[left, right]区间内的数字转换成整数 int calc(int l, int r) { int res 0; for (int i l; i r; i) { res res * 10 num[i]; } return res; } void check() { // 对于当前排列好的num数组枚举分割点 for (int i 0; i 7; i) { // 整数部分最多7位 int a calc(0, i); if (a n) break; // 关键剪枝整数部分已经大于等于N后续分割只会更大 for (int j i 1; j 8; j) { // 分子至少1位分母也至少1位 int b calc(i 1, j); int c calc(j 1, 8); if (b % c 0 a b / c n) { ans; } } } } // 生成全排列 void dfs(int pos) { if (pos 9) { // 排列完成 check(); return; } for (int i pos; i 9; i) { swap(num[pos], num[i]); dfs(pos 1); swap(num[pos], num[i]); // 回溯 } } int main() { cin n; dfs(0); cout ans endl; return 0; }这段代码清晰体现了“搜索剪枝”的思想。check函数中的if (a n) break;就是最关键的优化。实测下来对于N100这个算法能在毫秒级完成。如果没有这个剪枝时间会多出数倍。注意这里使用的是递归生成全排列。也可以使用C STL的next_permutation函数代码会更简洁。但手动实现DFS有助于理解回溯过程并且在需要嵌入更复杂剪枝时更灵活。4. 真题拆解二BFS与状态空间建模现在我们来看一道BFS的经典题目它考察的是如何将实际问题抽象成状态以及BFS中状态转移和判重的技巧。例题蓝桥杯历届试题——“九宫重排”八数码问题问题描述在3x3的棋盘上摆有8个棋子每个棋子上标有1至8的某一数字。棋盘上还有一个空格用0表示。空格周围的棋子可以移动到空格中。给定一个初始状态和一个目标状态找出最少移动步数。第一步状态定义与表示这是BFS最经典的应用场景之一。关键在于如何定义“状态”。很自然一个状态就是棋盘当前的样子。我们需要把3x3的棋盘表示成一个可以比较、可以哈希的数据形式以便进行判重。常用方法字符串表示将3x3矩阵按行展开成一个长度为9的字符串。例如状态[[1,2,3],[4,5,6],[7,8,0]]表示为123456780。字符串可以直接用作unordered_set的键来判重非常方便。整数表示将9个数字连起来看作一个9位数。但注意0在开头时比如012345678实际上是一个8位数需要特殊处理。通常不如字符串直观。二维数组/结构体可以但需要自定义哈希函数才能放入STL的哈希表中稍显麻烦。对于竞赛字符串表示法是首选因为它简单且C的unordered_setstring开箱即用。第二步状态转移如何走下一步在任何一个状态中我们找到空格‘0’的位置(x, y)。空格可以向上下左右四个方向移动前提是不出界。移动的本质是交换空格和其相邻格子的字符。 例如空格在(1,1)它向上移动就是与(0,1)的字符交换。我们需要在代码中模拟这个交换过程生成新的字符串状态。第三步BFS框架与判重这是一个标准的BFS求最短路径问题只不过节点是“状态”边是“一次移动”。队列存储待扩展的状态同时需要存储到达该状态的步数。可以用pairstring, int或者单独一个steps数组与状态映射。已访问集合unordered_setstring visited用于记录已经扩展过的状态避免重复入队和死循环。过程将初始状态和步数0入队并加入visited。当队列不为空时取出队首状态cur和步数step。如果cur等于目标状态返回step。否则找到cur中空格的位置枚举四个方向的移动。对于每个合法移动生成新状态nxt。如果nxt没有被访问过则将其和步数step1入队并标记为已访问。第四步代码实现与细节#include bits/stdc.h using namespace std; // 四个方向上、下、左、右 int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int bfs(string start, string target) { if (start target) return 0; queuepairstring, int q; // 状态和步数 unordered_setstring visited; q.push({start, 0}); visited.insert(start); while (!q.empty()) { auto [cur, step] q.front(); q.pop(); // 找到空格‘0’的位置 int pos cur.find(0); int x pos / 3; // 一维转二维行 int y pos % 3; // 一维转二维列 for (auto d : dirs) { int nx x d[0]; int ny y d[1]; if (nx 0 nx 3 ny 0 ny 3) { // 合法移动生成新状态 string nxt cur; int new_pos nx * 3 ny; // 二维转一维 swap(nxt[pos], nxt[new_pos]); // 交换空格和相邻格子 if (nxt target) { return step 1; } if (!visited.count(nxt)) { visited.insert(nxt); q.push({nxt, step 1}); } } } } return -1; // 无解 } int main() { string start, target; // 输入可能包含空格需要整行读入后去除空格 // 例如输入 123456780 和 123456708 cin start target; cout bfs(start, target) endl; return 0; }第五步进阶思考与优化上面的代码是BFS最基础的实现。对于3x3的八数码状态总数是9! 362880BFS完全够用。但这里有一些可以深入的点判重优化使用unordered_set在状态数多时可能有哈希冲突。可以使用康托展开Cantor Expansion将排列映射成一个唯一的整数排名然后用数组bool visited[362880]来判重速度更快。双向BFS从起点和终点同时开始BFS当两个搜索相遇时步数相加。这能极大减少搜索空间是解决此类问题的高级技巧。A*搜索利用启发式函数如每个数字到其目标位置的曼哈顿距离之和来优先扩展更有可能接近目标的状态可以比普通BFS更快找到解。这是八数码问题的更优解但实现比BFS复杂。在蓝桥杯赛场掌握基础BFS并写出无bug的代码是首要目标。如果时间允许可以尝试双向BFS它比A*更容易实现且优化效果显著。5. 搜索优化的核心剪枝策略实战精讲剪枝是搜索算法的灵魂是区分“暴力”与“智能”搜索的关键。不会剪枝DFS/BFS只能解决数据规模极小的问题。下面我总结几种蓝桥杯真题中最常见、最有效的剪枝策略。5.1 可行性剪枝提前判断当前分支是否可能产生解这是最直接、最常用的剪枝。在进入递归分支前先判断一下如果按照当前路径走下去绝对不可能达到目标那就直接返回。例题应用在“带分数”问题中如果当前构成的整数部分A已经大于等于目标N那么后续无论分子分母是什么A B/C都只会更大整个分支剪掉。另一个经典例子在“部分和问题”中给定数列判断能否选出若干个数使其和为K如果在递归中当前已选数字的和sum已经大于K那么后续无论加什么正数和都会更大分支剪掉。实现方式通常在递归函数的开头或进行下一次递归调用前加入一个if判断。5.2 最优性剪枝维护当前最优解及时淘汰劣质分支常用于求最优解最小值、最大值的问题。我们维护一个全局变量best记录当前找到的最优解。在搜索过程中如果发现当前路径的“代价”已经超过了best那么即使继续搜索下去得到的结果也不会比best更好可以剪枝。例题旅行商问题TSP的DFS求解。best记录当前最短回路长度。在递归中current_cost记录已走过的路径长度。如果current_cost best则剪枝。要点需要一个尽可能好的best初始值。有时可以先用一个贪心算法求一个解作为初始best能极大提升剪枝效率。5.3 顺序性剪枝与状态去重避免搜索等效状态很多问题的解空间存在对称性或者顺序无关性搜索等效状态是浪费。组合与排列求组合数C(n, m)时[1,2,3]和[1,3,2]是同一个组合。在DFS时我们可以强制规定每次选择的数字都比上一次大或从某个起始点开始递增选择这样就避免了生成顺序不同但集合相同的状态。例题从n个数中选m个数的所有组合。DFS函数增加一个参数start表示当前可以从第start个数开始选保证了选择的数字是递增的自然去重。对称性剪枝在一些棋盘类或图形类问题中状态可能旋转、翻转后等价。可以定义一种“标准形式”在搜索前或搜索后将状态转化为标准形式再判重。5.4 启发式剪枝与估值函数面向未来的“乐观估计”这是更高级的剪枝常用于最优解问题。我们设计一个估值函数f(state)它估计从当前状态state到达目标状态至少还需要多少代价必须是乐观估计即实际代价不会比f(state)更小。 如果当前已花费代价 f(state) best则剪枝。例题八数码问题的A*算法中启发函数h(state)如曼哈顿距离和就是一种估值函数它估计了从当前状态移动到目标状态至少需要的步数。难点设计一个既有效剪枝能力强又高效计算快的估值函数需要洞察问题本质。5.5 实战融合以“剪格子”问题为例蓝桥杯有一道经典题“剪格子”要求把网格数字分成两部分使得两部分数字和相等。我们可以用DFS搜索分割线。可行性剪枝如果当前路径上格子数字之和sum已经超过总和的一半剪枝。最优性剪枝题目要求分割的格子数最少。我们维护min_steps。如果当前已走步数steps min_steps剪枝。顺序性剪枝从左上角第一个格子开始深搜规定搜索方向顺序如右、下、左、上并记录访问状态避免重复走到已访问格子。连通性检查这是一个容易被忽略的强力剪枝。DFS只能保证搜索的部分是连通的但剩下的部分可能不连通导致非法解。可以在找到一组候选解后用另一个DFS/BFS检查剩余格子是否连通。如果不连通当前解无效。将这些剪枝策略结合起来就能让一个原本指数复杂度的搜索在规定时间内跑完较大的数据规模。6. 记忆化搜索当DFS遇见动态规划有些问题单纯的DFS会重复计算大量相同的子状态导致超时。这时记忆化搜索Memoization就派上用场了。它本质是递归形式的动态规划用一张表数组或哈希表把已经计算过的子问题的结果存起来下次遇到直接返回。核心思想在递归函数开头检查当前状态是否已经计算过。如果是直接返回存储的结果。否则执行计算并在返回前将结果存储起来。例题蓝桥杯真题——“地宫取宝”问题描述在一个n x m的格子迷宫里每个格子里有价值不同的宝贝。从左上角走到右下角每一步只能向右或向下。要求沿途拿走的宝贝数量正好是k件且每次拿走的宝贝价值必须比之前拿的所有宝贝价值都大。求有多少种不同的行动方案。这是一个典型的计数类DP问题但用DFS的思路去思考非常直观。 状态可以设计为dfs(x, y, cnt, max_val)表示从(x,y)位置出发已经拿了cnt件宝贝手上宝贝的最大价值是max_val走到终点(n-1, m-1)且满足条件的方案数。 如果不加优化这个DFS的复杂度是指数级的因为状态空间是n * m * k * (价值种类)。记忆化搜索实现状态设计dp[x][y][cnt][max_val1]。因为价值可能为0所以max_val从-1开始表示还没拿任何宝贝我们将其1映射到数组下标。递归过程如果(x,y)是终点判断cnt是否等于k返回1或0。否则查看dp[x][y][cnt][max_val1]是否已计算过初始化为-1。如果已计算直接返回。计算两种选择不拿当前格子宝贝方案数dfs(x1, y, cnt, max_val) dfs(x, y1, cnt, max_val)。如果当前格子宝贝价值grid[x][y] max_val还可以选择拿方案数dfs(x1, y, cnt1, grid[x][y]) dfs(x, y1, cnt1, grid[x][y])。将计算结果存入dp[x][y][cnt][max_val1]然后返回。效果通过记忆化每个状态最多只计算一次复杂度降为多项式级别O(n*m*k*C)C为价值范围完全可以承受。记忆化搜索 vs 递推DP记忆化搜索思维更符合直觉从大问题分解到小问题用递归实现。“需要什么算什么的DP”。递推DP需要明确计算顺序从基础状态递推到最终状态。选择对于状态转移依赖关系复杂或者不好确定遍历顺序的问题记忆化搜索往往是更简单、更不易出错的选择。在蓝桥杯竞赛中记忆化搜索是解决复杂计数问题的利器。7. 迭代加深与双向BFS应对深度与广度的挑战当搜索树很深但答案可能在较浅的层级时DFS可能陷入一个很深的分支出不来而BFS又可能因为状态空间太大导致内存爆炸。这时需要一些特殊的搜索策略。7.1 迭代加深搜索IDDFS结合了DFS的空间优势和BFS能找到最优解最短步数的优势。它从小到大逐渐增加搜索深度限制max_depth在每一层深度限制内进行深度优先搜索。过程设置深度限制depth 1。执行深度限制为depth的DFS。这个DFS在达到depth层时强制回溯不再深入。如果在这一层找到了解返回。如果没找到将depth回到步骤2。优点空间复杂度与DFS一样是O(depth)。当解在较浅层时能比盲目DFS更快找到。一定能找到最短解因为按深度递增搜索。缺点在深度限制以下的节点会被重复搜索多次深度为1,2,3,...时都会搜到浅层节点存在冗余计算。但对于状态分支因子大的问题深层节点数是指数级增长重复搜索浅层节点的开销相对可以接受。蓝桥杯应用常用于“最少操作步数”类问题且单次状态转移代价相同。例如一些变换类问题如果知道答案步数不会太多比如15步以内IDDFS是非常合适的。7.2 双向BFS普通BFS从起点开始单向扩展。如果状态空间很大队列可能会变得非常庞大。双向BFS同时从起点和终点开始进行BFS当两个方向的搜索相遇时就找到了最短路径。过程初始化两个队列q_start,q_end和两个已访问集合visited_start,visited_end。分别将起点和终点加入对应的队列和集合。每次选择节点数较少的那一端进行扩展平衡两端搜索进度。扩展节点时检查新状态是否出现在另一端的已访问集合中。如果出现则路径找到步数为两端步数之和1。优点搜索空间从O(b^d)降为O(b^(d/2))其中b是分支因子d是解深度。优化效果极其显著。缺点实现比单向BFS复杂需要维护两个队列和集合并且状态转移必须是可逆的从终点能反向推导出合法前驱状态。蓝桥杯应用适用于起点和终点都明确且状态转移可逆的问题如八数码、单词接龙等。当单向BFS面临状态爆炸时双向BFS是首选的优化方案。在实际编码中双向BFS的相遇判断是关键。一种简单的方法是在从一端扩展出新状态nxt时不仅检查是否在本端访问过也检查是否在另一端访问过。可以使用两个unordered_map不仅记录是否访问还记录到达该状态的步数相遇时相加即可。