蓝桥杯Python组的搜索题说白了就是BFS和DFS这两板斧。很多人刚开始备赛的时候觉得搜索很玄乎什么递归回溯、队列栈、状态标记听着就头大。但刷过几届真题之后你会发现搜索其实是蓝桥杯里性价比最高的考点之一——套路固定、模板清晰只要把框架吃透哪怕遇到没见过的题也能用搜索兜底拿分。这篇笔记我就把BFS和DFS从框架到实战完整捋一遍包含我备赛时踩过的坑和一些个人调试技巧适合正在备赛蓝桥杯Python组、对搜索还处于“看得懂但写不出”阶段的同学参考。1. 搜索在蓝桥杯里的地位与备赛思路1.1 为什么搜索是蓝桥杯Python组的重头戏先聊点实在的。搜索算法在蓝桥杯Python组里出现的频率非常高从填空题到编程大题都可能涉及。填空题那种8皇后、全排列、连通块染色之类的本质上就是DFS加回溯编程大题里的迷宫最短路径、岛屿数量、单词接龙这类题本质就是BFS。你仔细观察最近几年的真题就会发现搜索很少作为单独的压轴题出现但它经常作为解题的基础工具嵌在其他算法里比如图论题要跑连通性、状态压缩题要枚举状态、DP题有时候也得用DFS记忆化搜索来过渡。我个人的判断是搜索是蓝桥杯Python组必须拿下的基础分。因为搜索题的难度天花板不高但下限很低。框架背熟了哪怕是暴力搜索也能拿一部分分框架不熟写出来的代码大概率是运行时错误或者超时一分没有。而且Python写搜索其实有不少天然优势比如列表推导式处理状态、元组直接做哈希键、deque高效做BFS队列都比C要省很多代码量。所以Python选手在搜索题上完全没有理由丢分。1.2 从真题分布看BFS和DFS的考法我整理了一下蓝桥杯近几年的搜索相关题目大概能分成几个方向。第一种是纯模板类比如给你一个迷宫图求从起点到终点的最短步数这种直接用BFS就能过卡的是你对队列和标记数组的熟练度。第二种是连通性类比如统计一张图里有几个连通块、或者判断两个点是否连通DFS和BFS都能做但DFS写起来更直觉。第三种是状态枚举类比如凑数字、全排列、子集划分这类题明面上不说是搜索但你要枚举所有可能结果然后判断合法性和最优性这就是DFS加回溯的活。第四种是带条件的最短路类比如可以破坏障碍物、可以传送、可以瞬移这种就是在BFS状态里多加几个维度本质还是BFS。从得分难度来看第一类和第二类是必须拿满分的第三类需要练熟回溯模板第四类属于进阶练好了能在一等奖的竞争里拉开差距。下面我会按这个优先级逐步拆解。2. DFS深度优先搜索递归思维的核心2.1 DFS的框架与关键细节DFS深度优先搜索名字很唬人其实就是“一条路走到黑走不动了就退回来换一条路”。在代码层面DFS最常见的实现方式是递归。Python写递归非常直观先想清楚“这一步要做什么”再想清楚“递归边界是什么”。我习惯把DFS的模板拆成三块终止条件什么时候算搜索到头该记录结果或者返回了。剪枝条件哪些状态不用再搜了直接return。递归扩展从当前状态能走到哪些新状态逐个递归。举个例子计算从1到n的所有全排列这是最经典的DFS模板题n 3 path [] used [False] * (n 1) def dfs(depth): if depth n: print( .join(map(str, path))) return for i in range(1, n 1): if not used[i]: used[i] True path.append(i) dfs(depth 1) path.pop() used[i] False dfs(0)这里depth表示当前已经选了几个数字path存放当前排列used标记哪些数字已经被用过。所有全排列的枚举本质上就是在一棵递归树上做深度优先遍历。我特别想提醒的是“回溯”这两个字。在递归返回之后一定要把现场恢复原样也就是把used[i]改回False、把path.pop()掉否则下一轮搜索会带着上一次的状态继续跑结果必然错乱。我在初学阶段经常漏掉path.pop()导致输出结果一堆重复调试了很久才发现是回溯没做干净。2.2 回溯、剪枝与状态标记回溯是DFS的灵魂。很多初学者把DFS理解成单纯的递归枚举忽略了“回溯”这一步结果写出了一堆不正确的代码。实际上回溯做的事情是在当前路径走完之后把对共享状态的修改撤回去让另一条分支从原始状态开始探索。在蓝桥杯题目里回溯经常配合剪枝一起出现。剪枝的意思是提前判断某个分支不可能产生合法结果就直接跳过不要再递归下去了。举个例子枚举子集时如果当前已经选了k个数且超过目标值直接returnDFS解数独时当前位置如果填入某个数字导致同行同列冲突直接跳过这个数字。剪枝看起来很“聪明”但它的核心依据永远是题目条件。剪枝剪错了轻则答案错误重则漏掉正确答案。我建议新手先写不带剪枝的暴力DFS确保答案正确之后再加剪枝做优化。千万不要一开始就追求花哨的剪枝策略因为蓝桥杯的判分是看最终结果对的不看过程漂亮。另一个容易踩的坑是状态标记的方式。对于二维网格题很多人喜欢用二维visited数组来标记这没问题但要注意Python二维列表初始化的坑[[False] * m for _ in range(n)]是对的[[False] * m] * n是错的后者会让每一行指向同一个列表对象改一个值所有行都变。这个坑我在备赛期间不知道踩了多少次建议写成代码之前先心里默念一遍这个坑。2.3 典型DFS题型拆解岛屿数量与DFS序岛屿数量是一个非常经典的DFS题也可以看成连通块计数问题的入口。题目给你一个二维网格1代表陆地0代表水问有几块独立的岛屿。解法就是从每个未被访问的1出发用DFS把相邻的所有1都标记成已访问每完成一轮就计数加一。def num_islands(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) visited [[False] * cols for _ in range(rows)] count 0 def dfs(r, c): if r 0 or r rows or c 0 or c cols: return if grid[r][c] 0 or visited[r][c]: return visited[r][c] True dfs(r - 1, c) dfs(r 1, c) dfs(r, c - 1) dfs(r, c 1) for i in range(rows): for j in range(cols): if grid[i][j] 1 and not visited[i][j]: count 1 dfs(i, j) return count这个代码里有个很重要的细节上下左右四个方向的递归顺序。虽然对于“计数”结果来说方向顺序无所谓但如果你后面会接触到DFS序、拓扑排序之类的内容四个方向的遍历顺序会影响节点的访问顺序进而影响某些题目的答案。所以最好养成固定的方向写序习惯我一般按上、下、左、右写避免在压轴题里因为方向顺序不同导致一些隐蔽的错误。另外DFS在递归处理大网格时可能会遇到递归深度超限的问题Python默认递归深度只有1000左右遇到那种1000x1000的网格DFS递归到一半就RecursionError了。这时候有两个思路一是用sys.setrecursionlimit(1000000)把递归深度调大二是把递归改成显式栈迭代。前者简单粗暴后者更稳但显式栈写起来代码量更大初学者建议先用前者保平安后面有精力再练显式栈。3. BFS广度优先搜索最短路径利器3.1 BFS框架与队列实现细节BFS和DFS最大的不同在于遍历顺序DFS是纵向深入BFS是横向扩展。BFS天然适合求最短路径、最少步骤这类问题因为它从起点出发逐层向外扩展第一次到达终点的路径一定是最短的。BFS的框架比DFS更加固定核心就三样队列、标记数组、步数记录。from collections import deque def bfs_maze(maze, start, end): rows, cols len(maze), len(maze[0]) visited [[False] * cols for _ in range(rows)] q deque([(start[0], start[1], 0)]) # (行, 列, 步数) visited[start[0]][start[1]] True while q: r, c, step q.popleft() if (r, c) end: return step for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]: nr, nc r dr, c dc if 0 nr rows and 0 nc cols: if maze[nr][nc] ! # and not visited[nr][nc]: visited[nr][nc] True q.append((nr, nc, step 1)) return -1这里我强烈建议用collections.deque而不是列表模拟队列。用列表的pop(0)虽然也行但时间复杂度是O(n)数据量一大就容易超时而deque的popleft()是O(1)这个替换是零成本优化。还有一个细节我在入队前就标记visited而不是出队时标记。这是BFS里最重要的一个约定写法。如果你在出队时才标记已访问同一个节点可能会被多个分支重复加入队列导致进入死循环或者步数出现奇怪的结果。宁可多花几行代码也不要在“标记时机”上偷懒这个坑我印象太深刻了。3.2 步数记录的三板斧分层、队列携带、距离数组BFS求最短步数常见的记录方式有三种我都用过各有适用场景。第一种是上面样例里的写法把步数作为元组的一个字段放进队列里每扩展一层就加一。这种写法最直观适合新手缺点是队列元素变大了不过对于蓝桥杯的数据规模来说完全够用。第二种是分层扩展写法用while循环加for _ in range(len(q))每层整体往外扩一次。这种写法适合需要区分“层”的题目比如让你输出最短路径经过的每一层节点个数。第三种是单独维护一个距离数组dist初始化为-1或一个很大的数每次扩展到新节点时dist[nr][nc] dist[r][c] 1。距离数组写法的好处是最终不光能求最短步数还能用来回溯输出具体路径。我个人在蓝桥杯里最常用的是第一种和第三种。第一种写起来快、不容易错第三种适合需要路径回溯的题。如果你已经有一定基础建议直接练第三种因为在部分真题里题目不满足只给终点步数会要求你给出整条最短路径。3.3 BFS的常见变化与状态压缩蓝桥杯考BFS很少是裸的迷宫题它经常给你加各种条件。比如迷宫里有传送门、有钥匙、有障碍可以打破这些条件本质上都是在改造“状态”这个定义。普通BFS的状态是(行, 列)加上钥匙之后状态就变成(行, 列, 已经持有的钥匙mask)这里mask就是状态压缩。Python里用整数做掩码非常爽比如拿到了第i把钥匙就执行mask | (1 i)判断有没有第i把钥匙就用if mask (1 i)。然后visited数组也要相应变成三维visited[r][c][mask]。我刷过一道真题题目大意是在迷宫里需要先拿钥匙再开锁那题如果不用状态压缩普通二维visited会漏掉“走过同一点但持有钥匙状态不同”的情况导致永远搜不到答案。这也是BFS题最容易翻车的地方状态定义不全。所以在拿到BFS题的时候第一步不是急着写代码而是先想清楚“状态由哪几个维度构成”。维度可以是坐标、剩余步数、已经持有的物品、朝向、血量等等。状态定义对了BFS就成功了一大半。3.4 双向BFS与进阶优化当搜索空间特别大时单向BFS可能会超时这时候可以尝试双向BFS。双向BFS的思路是从起点和终点同时开始广搜两边交替扩展直到两个方向的搜索范围相遇。因为BFS每层的节点数是指数增长的双向BFS通常能把搜索空间减少到原来的平方根量级速度提升非常明显。蓝桥杯里很多最短步数题如果数据规模卡在几千上万单向BFS可能勉强能过但如果到几万甚至更多双向BFS就是救命稻草。实现双向BFS的时候我习惯用两个队列和两个visited字典Python里字典代替数组的好处是稀疏状态也能存。不过我也要泼一盆冷水双向BFS代码量比单向大不少而且要注意两个方向交替扩展的步调。我建议冲刺省一、国赛的选手认真掌握但如果目标是省二省三先把单向BFS写稳比在考场上纠结双向BFS更实际。4. 实战解析三阶段刷题路线与要点4.1 入门题迷宫最短路径与连通块入门阶段的目标是把DFS和BFS模板写到“闭着眼都能背”的程度。题目选择我不建议一上来就刷难题而是找几道最朴素的模板题比如标准的迷宫最短路径、二维网格的连通块计数。这类题的输入输出都比较规矩不会给你使绊子。刷题时要有意识地固定自己的代码风格。比如方向数组统一写成[(−1,0), (1,0), (0,−1), (0,1)]队列里元素的取值顺序统一是(row, col, step)递归函数参数顺序统一是“坐标在前辅助变量在后”。风格统一的好处是省脑力在考场上你不需要再去想自己上次是怎么写的直接肌肉记忆输出。这个阶段我个人的习惯是拿到一道题先不急着提交而是在草稿纸上把样例的搜索过程画一遍标出每层的节点。这样做看起来很费时间但对理解BFS的层级扩展和DFS的递归回溯帮助极大。我也建议你们试试。4.2 进阶级带权迷宫与多状态搜索入门模板熟练之后就可以挑战进阶题了。我推荐两类练习方向。第一类是带权迷宫也就是每个格子走过去要消耗不同的体力值或时间问最小代价。这种题严格来说不叫BFS而是Dijkstra最短路但它可以看成BFS的变种用优先队列替代普通队列即可。Python里可以用heapq实现优先队列代码结构和BFS非常像。第二类是多状态搜索就是我前面提到的状态压缩BFS。练习这类题时先不要急着看答案自己试着定义状态维度然后写visited数组然后再调通。这类题是真正考验你“状态设计能力”的而在蓝桥杯里这个能力非常值钱。进阶级刷题量建议在10道以上不要贪多关键是每道题都要吃透。吃透的意思是能用自己的话解释为什么状态要这么定义、为什么这样标记不会漏状态、为什么答案不会出错。4.3 冲刺级搜索与其他算法的结合真正拉开差距的题目往往不是单纯的搜索而是搜索和二分、DP、贪心、枚举等技巧的结合。我印象最深的一类题是“二分答案DFS判定”。比如让你求一个阈值使得在某种规则下能达成某个目标直接搜阈值会超时但用二分枚举阈值再用DFS检查可行性就快很多。这种题看起来是搜索题实际上是二分模板套DFS。还有一种题型是“DFS枚举DP验证”先搜索所有可能的组合再用DP判断组合的合法性或最优性搜索负责枚举空间DP负责判断两者结合能解决很多看似无解的搜索题。这个阶段我不建议再大量刷题而是应该把历届真题按题型分类总结整理出自己的一套解题思维链。我备赛时做了一个简单的表格分列“题目类型、核心算法、状态定义、复杂度优化”每做一道就填一行。到了考前冲刺阶段直接翻这个表比重新刷一遍题高效得多。4.4 蓝桥杯搜索题的常见提示词识别读题的时候有些词基本就是搜索题的“信号”我在备赛时总结了一些高频提示词出现“最短步数”、“最少操作次数”、“最少时间”时优先考虑BFS。出现“连通”、“岛屿”、“块数”、“是否可达”时DFS或BFS皆可但DFS写起来更快。出现“所有可能”、“全部方案”、“枚举所有组合”时想DFS加回溯。出现“状态变化”、“带钥匙”、“带血量”、“带瞬移”时想BFS加状态压缩。这个列表很粗糙也有例外但它能帮你在考场上快速锁定方向。搜索题最怕的不是不会写而是在几种算法之间犹豫不决浪费大量时间。5. 备赛中的常见问题与排查技巧5.1 递归爆栈与性能瓶颈怎么解决Python的递归深度默认在1000左右这在蓝桥杯的某些题目里是个大问题。遇到DFS要遍历一个比较深的图或者递归函数本身有较深的嵌套时直接RecursionError崩溃代码还没出结果就先挂了。最直接的解决办法是sys.setrecursionlimit(1000000)写在递归函数之前这个技巧在蓝桥杯考场上是合法的也是很多Python选手的常规操作。但我要说实话把递归深度调大只是治标如果搜索空间本身很大过深的递归还会带来巨大的函数调用开销性能反而更差。真正治本的做法是改成迭代式DFS也就是自己维护一个栈。思路是把递归里“当前状态”和“遍历进度”都放到栈里用循环模拟递归调用和返回。这个写法更绕但性能稳定。我的建议是如果题目数据规模比较小直接用递归加setrecursionlimit就够了如果数据规模大且拓扑很深务必改用迭代栈不要在递归上硬刚。5.2 超时与内存的正确排查姿势搜索题最常见的两个错误是超时和内存超限我先说超时。超时的原因通常有两个一是状态标记不到位导致大量重复搜索二是剪枝条件不够强搜索树太庞大。排查重复搜索的时候我习惯在代码里加一个计数器统计每个状态被访问的次数。如果某个状态被访问多次说明标记逻辑有问题。排查剪枝不够强的时候我会先把题目给的数据范围代入复杂度估算出最坏要搜多少个状态如果数量级太大就得回头继续加剪枝。内存超限在Python里一般表现为MLE大多数情况是visited数组建得太大或者队列里堆积了太多元素。我遇到过一些同学为了省时间把很多中间结果缓存在字典里结果内存爆了。这时候思路就反过来用时间换空间别把数据都存下来宁可多跑一遍。5.3 调试搜索代码的独门技巧搜索类题目调试起来很折磨人因为递归过程太抽象了单步调试根本追不过来。我总结了一套自己的调试方法很土但很有效。第一招是“小样例暴力输出”在递归函数入口打印当前状态比如print(r, c, step, path)然后把样例数据改到很小比如3x3网格一步步观察输出是否符合预期。第二招是“计数对比法”如果题目要求统计所有方案数可以先用暴力DFS写一个不带剪枝的版本和优化后版本跑同一个样例看答案是否一致如果不一致说明剪枝条件写错了。第三招是“注释法”把剪枝代码一行行注释掉看哪一行注释之后答案变了就说明bug在那附近。这三招交互使用基本上能解决90%的调试问题。我备赛后期基本不依赖IDE的断点调试功能都是靠这几招。5.4 边界条件与输入处理的那些坑蓝桥杯的搜索题输入处理也是一个容易出错的地方。你永远要假设输入的第一行可能带空格网格行可能是字符串而不是字符列表可能存在空行可能有多组测试数据等。我的处理习惯是尽量提前统一输入格式读网格用[list(input().strip()) for _ in range(n)]读数字用list(map(int, input().split()))如果题目没说保证输入合法就顺手加一个简单的边界判空。这些细节看似琐碎但能省下大量因为输入解析错而提交失败的冤枉时间。边界条件方面我列几个必查项起点就是终点的情况BFS返回0是否合理。网格不存在合法路径时返回什么题目是否要求输出特定值。第一步就撞墙的情况。迷宫里所有格子都是障碍的情况。递归函数的出口顺序是先判断越界还是先判断访问过顺序不同可能导致越界数组访问报错。每次写完搜索代码我建议对着这个清单自查一遍再提交能大幅降低无谓的罚时。6. 我个人在搜索题上的心得与建议搜索算法说来说去就那么点东西但真正熟练和“知道”之间隔着大量练习。我备赛蓝桥杯期间最大的体会是搜索题的代码模板固然重要但更重要的是状态设计能力和边界条件意识。很多选手卡在BFS题上往往不是不会写队列而是没有想清楚“状态”包含哪些维度。如果把这道坎迈过去后面刷搜索题几乎是一马平川。另外我想分享一个小技巧考前一周不要刷新题而是把之前做过的搜索题的主函数代码重新默写一遍。默写的时候不要看原代码写完之后再对比找出自己记忆模糊的部分。这个过程看似机械但能够在考场上把“肌肉记忆”变成真正的得分保证。再补一个非常实用的习惯把常用的BFS方向数组、DFS回溯模板、状态压缩掩码操作单独整理成一个代码备忘录考前打印出来或者存到本地。蓝桥杯是允许带纸质资料进考场的但依赖纸质资料不如把这些模板熟记在脑子里。备忘录的真正价值是让你在考前最后一天还能从头到尾快速过一遍所有框架。搜索题是蓝桥杯Python组里投入产出比最高的板块之一希望这篇笔记能帮你少走一些弯路。每个人踩过的坑不太一样如果你在练习时发现了其他奇葩问题欢迎在实践中总结成自己的避坑手册那才是真正属于你的备赛财富。