话不多说直接进入主题。蓝桥杯Python组搜索题几乎是必考题型DFS和BFS问得又勤又深。省赛的填空题靠暴力搜索出答案大题靠BFS解决最短路径DFS解决方案枚举和连通块问题。这篇是《蓝桥杯Python备赛笔记》系列第六篇我把搜索这个专题从头到尾整理了一遍用最直白的方式把DFS、BFS的思路和模板拆给你看可以直接当成复习提纲来用。1. 蓝桥杯Python搜索题到底在考什么1.1 从一道迷宫题看清搜索的本质先别急着背模板得先搞懂搜索题在蓝桥杯里长什么样。最简单的形式就是给一个二维网格比如一个迷宫里面有起点有终点有些格子能走有些格子是障碍物问从起点到终点能不能走到最短走几步。这类题换个包装就是蓝桥杯省赛的大题。这类问题的本质是把所有可能走的路径当成一棵树来遍历。你站在起点面临若干分支——往上走、往下走、往左走、往右走。每走一步又会遇到新的分支。搜索算法要做的就是把这棵“路径树”全部走一遍找到满足条件的路径。这里有个关键概念状态。在迷宫题里状态就是“当前在第几行第几列”。更复杂的搜索题状态可能是一个数值、一个字符串、一组排列甚至是一个经过压缩编码的棋盘局面。DFS和BFS的区别只是遍历这个“状态树”的顺序不同但最终都能遍历完整棵状态树。1.2 蓝桥杯的数据范围决定了搜索的地位很多人会问现在算法题那么多为什么非要学搜索蓝桥杯的特点在于题目的数据范围设计。省赛和国赛里很多题n的范围只有10到20比如问你有多少种排列方式、多少种走法。这种范围动态规划一时半会儿想不出状态转移方程贪心又容易错最稳妥的办法就是暴力搜索。搜索就是这类题目的“保底答案”。就算你想要的算法没想出来只要把状态空间设计对用DFS枚举所有可能再用BFS求最短至少能拿到大部分分数。尤其Python组题目给的运行时间往往比C组宽裕一些这就给搜索留了生存空间。另一个原因是搜索本身是很多高级算法的基础。记忆化搜索就是带缓存的DFS很多图论题的本质是BFS或DFS的变体树上的遍历更是DFS的直白应用。你把DFS和BFS吃透了后面学动态规划、学最短路算法都会顺利很多。2. DFS一条路走到黑的递归艺术2.1 一份能直接套的DFS递归模板DFS深度优先搜索的核心思想是沿着一条分支一直深入下去直到走不下去再回头换一条分支继续。在代码层面最自然的实现方式就是递归。来看最基础的一份DFS框架。假设我们有一个状态state目标是判断是否存在某个终止状态满足条件def dfs(state, visited): # 1. 判断是否已经是终点状态 if is_goal(state): return True # 2. 标记当前状态已访问防止走回头路 visited.add(state) # 3. 枚举当前状态能到达的所有邻接状态 for next_state in get_next_states(state): # 跳过已经访问过的状态避免死循环 if next_state not in visited: # 4. 递归深入下一层 if dfs(next_state, visited): return True # 5. 如果所有分支都不满足撤销访问标记可选返回失败 # visited.remove(state) # 这行在部分场景需要放开 return False注意框架里的visited.remove(state)是否要写取决于题目要求的是“是否存在一条可行路径”还是“是否存在一种排列方案”。前者棋盘类问题往往不需要删掉标记因为走过就相当于占用后者排列组合类问题必须回溯删去标记让同一个元素能被后续分支重新使用。这个模板看着简单但真正重要的是理解递归的执行顺序。每调用一次dfs就相当于在状态树里往下走了一层。递归深度等于搜索深度所以一旦搜索空间很深就要小心后面提到的递归深度限制问题。2.2 回溯和剪枝让DFS真正有战斗力DFS最经典的战场是排列组合问题。蓝桥杯的填空题里经常出现类似“数字1到4有多少种排列方式”这种题n不超过10完全可以直接DFS暴力枚举。这里的核心操作就是回溯。举一个全排列的例子。给定nums [1, 2, 3]要输出所有排列方式n len(nums) used [False] * n path [] def dfs(idx): if idx n: print(path.copy()) return for i in range(n): if not used[i]: used[i] True path.append(nums[i]) dfs(idx 1) # 回溯撤销当前选择让下一次分支可以用这个数 path.pop() used[i] False dfs(0)path.pop()和used[i] False这两行就是回溯的核心。它们的作用是在递归返回后把现场恢复成调用之前的样子这样同一个for循环的下一次迭代才能正确尝试新的分支。如果去掉回溯你会发现第一次递归就占用了所有数字后续分支什么也做不了。所以记住一句话选了要撤销才算完整回溯。剪枝则是DFS的加速器。所谓剪枝就是发现某些分支根本不可能产生有效答案直接跳过不再递归进去。比如求一个集合的子集且要求元素和不超过某个值当前累计和已经超过阈值那再往下加只会更大这时候直接return就是一种剪枝。2.3 矩阵DFS连通块蓝桥杯高频考法蓝桥杯特别喜欢考二维矩阵上的DFS连通块问题。典型场景是一张地图上分布着障碍物和草地让你数一数有多少块连通的区域、某个连通区域有多大。这类题的解法套路极其固定核心是“四个方向递归 走过就标记”。directions [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(grid, i, j): n, m len(grid), len(grid[0]) # 越界判断 if i 0 or i n or j 0 or j m: return # 如果是障碍点或已访问直接跳过 if grid[i][j] # or grid[i][j] visited: return # 标记为已访问 grid[i][j] visited # 递归访问四个方向 for dx, dy in directions: dfs(grid, i dx, j dy)这段代码是很多蓝桥杯真题的原型。你只需要把grid[i][j]的判定条件换成具体题目里的“可通行条件”即可。比如题目给的矩阵可能是0表示空地1表示墙那判断条件就写成if grid[i][j] 1: return。这里有一个容易踩的坑标记已访问的时机。一定要在进入递归前把当前格子标记掉而不是在递归返回后。如果等递归执行完再标记同一次递归可能反复访问同一个格子直接导致栈溢出或超时。2.4 连通块问题的完整示例假设给定一个矩阵.表示空地X表示障碍统计空地连通块个数。完整代码如下n, m map(int, input().split()) grid [list(input().strip()) for _ in range(n)] directions [(-1, 0), (1, 0), (0, -1), (0, 1)] ans 0 def dfs(i, j): if i 0 or i n or j 0 or j m or grid[i][j] ! .: return grid[i][j] V for dx, dy in directions: dfs(i dx, j dy) for i in range(n): for j in range(m): if grid[i][j] .: ans 1 dfs(i, j) print(ans)这里用grid[i][j] V原地修改矩阵来标记访问省掉了额外的visited数组在蓝桥杯里完全够用也不需要额外维护一套坐标去重逻辑。如果题目要求不修改原矩阵那就单独开一个二维布尔数组visited [[False] * m for _ in range(n)]。矩阵DFS的复杂度是 O(n×m)每个格子最多访问一次。在 1000×1000 的矩阵里Python 递归实现的 DFS 可能稍慢但在蓝桥杯的常见范围几百乘几百内性能没有问题。3. BFS逐层扩张的最短路径引擎3.1 一份能直接套的BFS队列模板BFS广度优先搜索的思路和DFS正好相反。它是一层一层往外扩散先访问距离起点为1的所有节点再访问距离为2的所有节点以此类推。这种逐层扩散的特性让BFS天然适合求最短路径——第一次到达目标节点时走的步数一定是最少的。实现BFS必须借助队列Python里推荐用collections.deque因为它支持 O(1) 的左右两端操作比直接用list做队首弹出要快很多。from collections import deque def bfs(start_state): # 初始化队列和距离字典 q deque([start_state]) dist {start_state: 0} while q: state q.popleft() # 如果当前状态是目标直接返回步数 if is_goal(state): return dist[state] for next_state in get_next_states(state): if next_state not in dist: dist[next_state] dist[state] 1 q.append(next_state) return -1 # 找不到目标这个模板里的dist字典既记录了每个状态的最短距离又起到了visited的作用——只要某个状态曾经进入过队列就说明已经找到了到达它的最短路径不需要再次入队。这里有一个我特别想强调的点BFS中每次从队列弹出一个状态它对应的距离就是当前层数不会出现同层状态互相覆盖的问题。所以用dist[next_state] dist[state] 1来做层数标记是绝对安全的不用担心更新冲突。3.2 迷宫最短距离的完整实现给你一个经典的迷宫最短路径题给定一个n行m列的平面图S是起点E是终点.是可走格子#是墙求从起点到终点的最短步数不能走到墙外。from collections import deque n, m map(int, input().split()) maze [list(input().strip()) for _ in range(n)] directions [(-1, 0), (1, 0), (0, -1), (0, 1)] # 找到起点和终点 for i in range(n): for j in range(m): if maze[i][j] S: sx, sy i, j elif maze[i][j] E: tx, ty i, j dist [[-1] * m for _ in range(n)] dist[sx][sy] 0 q deque([(sx, sy)]) while q: x, y q.popleft() if x tx and y ty: print(dist[x][y]) break for dx, dy in directions: nx, ny x dx, y dy # 越界或撞墙 if 0 nx n and 0 ny m and maze[nx][ny] ! #: if dist[nx][ny] -1: dist[nx][ny] dist[x][y] 1 q.append((nx, ny)) else: print(-1)这里用二维列表dist初始化为-1表示“还没到过”。每个格子的距离第一次被更新时就是到达它的最短步数所以之后不需要再更新也不会重复入队。BFS解迷宫最需要留意的边界条件有两个一是坐标越界判断Python比较的是0 nx n这样的链式不等式很多新手容易写反二是maze[nx][ny] ! #这个墙的判断要排除掉起点和终点之外的不可走格子保留起点和终点本身。3.3 状态压缩让BFS处理更复杂的状态很多蓝桥杯题目不会只让你在二维网格上走而是把“状态”设计得更抽象。比如八数码问题一个3×3方格里有8个数字和一个空白格问要移动多少步才能达到目标排列。这时每个状态就是整个盘面的排列顺序如果拿二维列表当字典的key速度很慢而且嵌套结构容易出错。这时候就需要状态压缩。把整个盘面编码成一个字符串比如123456780代表目标状态那么dist字典的key就是字符串进行状态转移时根据字符串中0的位置尝试和上下左右的数字交换位置生成新的字符串。from collections import deque start .join(input().split()) # 读入初始盘面字符串 target 123456780 directions [-3, 3, -1, 1] # 上下左右3x3盘中对应索引变化 def get_next_states(s): i s.index(0) res [] for d in directions: j i d # 越界处理左右移动不能跨行 if not (0 j 9): continue if (d -1 and i % 3 0) or (d 1 and i % 3 2): continue if i % 3 2 and d -1: continue if i % 3 0 and d 1: continue # 交换字符 lst list(s) lst[i], lst[j] lst[j], lst[i] res.append(.join(lst)) return res q deque([start]) dist {start: 0} while q: cur q.popleft() if cur target: print(dist[cur]) break for nxt in get_next_states(cur): if nxt not in dist: dist[nxt] dist[cur] 1 q.append(nxt) else: print(-1)这个例子真正想说明的是BFS本身并不复杂复杂的是如何高效地表示状态并生成下一步状态。字符串、整数位运算都是常用的状态压缩手段。一旦记住了“用状态做key 队列 距离字典”这个三层结构BFS类的难题你已经解决一大半了。4. DFS和BFS怎么选别再纠结4.1 一张对照表理清适用场景学完两个算法之后最常见的问题是这题到底用DFS还是BFS其实只要记住几个硬性判断标准就可以快速决策。我先给你一张对照表判断维度DFSBFS实现方式递归或显式栈队列遍历顺序深度优先深入一条分支到底从近到远逐层扩张适用场景枚举所有方案、连通块判断、树的前序/中序/后序遍历最短路径、最少步数、层序遍历、拓扑排序空间占用一般为栈深度可能很大每层节点数量可能很大是否适合求解最短路不适合要走遍所有可能才知道最短非常适合第一次到达终点即最短典型蓝桥杯题型全排列枚举、数独求解、岛屿数量、剪邮票迷宫最短路、八数码、红绿灯状态搜、最少交换次数一个大胆的简化判断法题目里出现了“最短”“最少”“最快到达”这类词直接上BFS题目里出现了“一共有多少种”“列举出所有方案”“是否存在一条路径”这类词优先考虑DFS。还有一类题需要结合两者先用DFS确定搜索状态的形状比如剪邮票时从12个格子选5个再用BFS判断这5个格子是否连通。这种混合思路在蓝桥杯中不算罕见。4.2 从蓝桥杯实际题目看选型思路拿大家比较熟悉的《剪邮票》这题举例。题目大致是12张邮票连成3×4的网格要从中剪下5张连在一起的邮票问有多少种剪法。这里每一张邮票都不一样5张连在一起必须相邻。如果直接用DFS去数会很繁琐因为选5张邮票相当于枚举组合再判断组合是否连通。这个题最流畅的解法是用DFS枚举从12个数中选5个数的组合把选中的5个位置在网格中标记出来再用BFS或DFS去检查这5个位置是否连通。枚举组合用DFS的排列框架连通性检查用DFS连通块模板两者配合才能稳定做对。如果只用纯DFS枚举或者纯BFS检查都会卡在“组合去重”或“连通性判断”这两个环节上。再举一类小题给定一张图问从1号点出发能不能走到所有点。这种“可达性”问题用DFS和BFS都可以做。如果同时要求输出一种可行路径DFS更方便因为递归天然记录了路径如果要求输出最短路径BFS更合适因为BFS搜索树中第一次遍历到目标节点的路径就是最短路径。记住这个规律之后你基本不用再为选DFS还是BFS纠结。真正需要多花时间的反而是怎么把一个题目的状态表示写对。5. 备赛中踩过的坑当成反面教材5.1 递归深度爆炸你需要注意这个细节Python默认的递归深度上限大约是1000层。蓝桥杯的DFS题数据范围稍微大一点比如在1000×1000的网格上做连通块统计递归深度就可能顶到上限直接报RecursionError。我一直到踩了两三次这个坑之后才真正重视起来。最靠谱的解法是在代码开头加上import sys sys.setrecursionlimit(1_000_000)这个设置会把递归深度上限调到100万对绝大多数蓝桥杯题目都足够安全。不过要注意设置递归深度上限只是“允许”Python递归到这么深不等于不会超内存。每一层递归都会占用一些栈空间如果网格巨大还是需要考虑换成显式栈来实现DFS或者改用BFS。显式栈DFS的模板其实不难就是把递归过程手动用list模拟。矩阵连通块问题改成显式栈之后内存占用稳定也不会出递归深度的问题。实际备赛中我建议先无脑加上setrecursionlimit如果提交后出现内存问题再考虑改成显式栈或BFS也不迟。5.2 visited数组位置写错整个搜索全乱visited标记的位置是搜索题最容易出错的地方。我在刚开始学搜索时经常把visited的更新写在递归调用之后的某个位置导致同一个节点被反复访问程序跑了老半天也出不来。正确的做法是进入递归前先更新visited递归返回后再恢复这才符合“先占坑再前进”的原则。举个例子在DFS全排列中used[i] True必须在调用dfs(idx 1)之前执行而恢复现场写在调用之后。如果你把顺序写反了比如在调用之后才设置used[i] True那递归过程中used数组一直是全False每个分支都会尝试所有数字最终产生大量重复排列。BFS里的visited和dist是合二为一的。当某个状态第一次入队时就要立刻设置距离并标记这一点同样要牢记。我最开始写BFS时经常先入队再在弹出的时候判重这就会导致同一个状态被加入队列很多次队列越来越大最终既慢又可能出错。记住入队即标记弹出即判断目标。5.3 方向数组和坐标边界最容易疏忽的地方因为坐标写错导致越界报错或者答案不对这个问题几乎每个搜索初学者都遇过。方向数组的定义方式很多我推荐统一用[(-1, 0), (1, 0), (0, -1), (0, 1)]也就是上、下、左、右不要随意改变顺序避免记混。在矩阵题里坐标i表示行j表示列判断越界时一定要用0 i n和0 j m同时判断。很多错解把m和n用反了导致列数超过行数的数据直接数组越界。建议一开始就统一把变量命名为rows和cols可读性高也减少出错概率。还有一个隐藏很深的坑左右移动不能跨行。如果题目允许你在一维数组上左右移动比如八数码中的移动空白格那么当空白格在第一列时向左移动就会“穿越”到上一行的最后一个位置这是不允许的。判断方式是根据当前位置的列号j当j % 列数 0时禁止左移j % 列数 列数-1时禁止右移。5.4 输入读取优化不要被大输入卡住蓝桥杯Python组的输入规模有时很大尤其搜索题里涉及的矩阵可能有几百行甚至上千行。如果使用基础版input().strip()循环读在数据量上来时可能会超时尤其是当循环中还有大量计算时。我实测过直接用sys.stdin.readline比input()快一些。高效的读法有两种。一种是全部读进来再按行处理import sys data sys.stdin.read().split()返回值是一个字符串列表可以直接从中按顺序取数据。另一种是逐行读取但使用sys.stdin.readlinen, m map(int, sys.stdin.readline().split()) grid [list(sys.stdin.readline().strip()) for _ in range(n)]这种写法在竞赛中被大量使用性能稳定。蓝桥杯本身不会刻意卡Python的常数但能快一点是一点毕竟搜索题往往需要把时间留给算法本身。6. 一道压轴综合题完整拆给你看6.1 题目设计与思路分析我们综合运用DFS和BFS来做一个典型的综合题。设计这样一个场景有一个n × m的网格部分格子是墙#其余是空地.网格中有一个入口S和一个出口E。此外还有一个传送门T踩上传送门后会自动传送到另一个传送门所在位置传送本身也消耗一步。问从入口到出口的最短步数。这题的难点在于传送门的存在让状态不再是单纯的坐标还需要考虑“是否已经使用过传送门”。如果直接走BFS从传送门A跳到传送门B之后后续的搜索仍然可以用传送门B跳到传送门A这会造成循环。最简单的处理办法是在进入传送门时进行一次特殊转移从传送门A跳到传送门B后不再允许原地再传回去但这在网格遍历中实现起来稍显繁琐。更稳妥的思路是把传送门拆成两个可重复访问的节点。搜索时当走到传送门A时把“传送”也当作一种移动方式生成一个新坐标传送门B的位置。因为BFS的dist字典天然记录状态访问情况当传送门B已经访问过时就不会重复入队。这样即使两个传送门反复横跳也在BFS的剪枝范围内被限制住。这个题可以看成是迷宫最短路径的变体用到的核心模块就是前面写的BFS模板。你只需要修改get_next_states这一层让它额外处理传送逻辑即可。6.2 完整代码与逐段解读import sys from collections import deque sys.setrecursionlimit(1_000_000) def solve(): data sys.stdin.read().split() n int(data[0]) m int(data[1]) grid [] portals {} idx 2 start None end None for i in range(n): row list(data[idx]) idx 1 for j, ch in enumerate(row): if ch S: start (i, j) elif ch E: end (i, j) elif ch T: # 收集传送门坐标 if T1 not in portals: portals[T1] (i, j) else: portals[T2] (i, j) grid.append(row) # 记录两个传送门的对应关系 t1, t2 portals[T1], portals[T2] warp {t1: t2, t2: t1} directions [(-1, 0), (1, 0), (0, -1), (0, 1)] dist [[-1] * m for _ in range(n)] dist[start[0]][start[1]] 0 q deque([start]) while q: x, y q.popleft() if (x, y) end: print(dist[x][y]) return # 普通移动 for dx, dy in directions: nx, ny x dx, y dy if 0 nx n and 0 ny m and grid[nx][ny] ! #: if dist[nx][ny] -1: dist[nx][ny] dist[x][y] 1 q.append((nx, ny)) # 传送门特殊移动 if (x, y) in warp: nx, ny warp[(x, y)] if dist[nx][ny] -1: dist[nx][ny] dist[x][y] 1 q.append((nx, ny)) print(-1) if __name__ __main__: solve()这段代码最核心的思想是在BFS的每一层扩展中除了四个方向的普通移动还额外增加了一种“瞬移移动”。因为传送门的起点到终点之间消耗1步相当于一条额外的边。BFS把这种特殊边和普通边放在同一个层级体系里处理天然保证最短步数的正确性。这里有一个细节值得注意传送门坐标是用dict来表示对应关系的。warp[(x, y)]能快速找到另一个传送门位置。如果你的图里不止一个传送门还可以把传送门列表放在数组里遍历每个传送门作为可能的传送目标灵活度更高。6.3 这类题还能怎么变形一个传送门只是起点蓝桥杯的搜索题常常在此基础上继续加限制、加条件但万变不离其宗。第一种变形是有多个传送门且有使用次数限制比如只能使用一次传送。这时状态需要额外记录一个布尔值used_warp用(x, y, used_warp)作为BFS队列元素和dist字典的key。本质上只是把状态从二维升到三维BFS模板无需改动。第二种变形是传送门有冷却时间比如使用后要等三步才能再次使用。这种题通常会引入时间维度BFS的层数自然代表时间状态里可以直接用“还有几回合冷却”来编码。第三种变形是把传送门换成“翻转道路”的机关踩到某格后令特定方向的墙暂时消失。这本质上还是在BFS状态里增加一个环境标记字段每一次状态转移时都基于当前环境判断可走性。这些变形的难度都在状态设计上而不在BFS框架本身。所以我在备赛时会把上面这份模板当成基线遇到新题首先思考“当前状态是什么如何用元组或字符串表示邻居有哪些”这三点想明白三分之二的题目就能直接套模板做出来。最后说点实在的心得从我开始刷蓝桥杯到现在最大的体会是搜索题不会太难也不会太简单。难在状态设计简单在模板固定。你先吃透DFS的递归回溯框架和BFS的队列距离框架再把矩阵连通块和状态压缩这两个高频场景练熟基本可以覆盖蓝桥杯90%以上的搜索题。建议你在OJ上找至少十道搜索题练手不要贪多每道题都严格按照模板来实现把visited的位置、递归返回的条件这些细节刻进肌肉记忆。等比赛真遇到搜索题时你会发现思路来得非常快敲代码的时候几乎不用思考那些基础框架了。