从走迷宫到搜索思维DFS在算法竞赛中的完全拆解不知道你有没有这种经历刷题网站上碰到“给定一个 n*m 的网格从左上角走到右下角遇到 # 不能走问能不能走通”这类题第一反应是套 BFS 模板因为脑子里的刻板印象是“最短路径 BFS”。结果题目一变要求输出所有可行路径、或者求有多少种走法、甚至地图里加了传送门BFS 一下就变得别扭了。这时候你才发现DFS 这套递归搜索的思路才是理解迷宫问题的底层钥匙。这篇文章我想从头到尾聊聊算法竞赛里怎么用 DFS 解迷宫问题。不会只贴一段能跑的代码就完事而是把递归函数怎么设计、访问标记什么时候恢复、剪枝到底剪在哪个环节、以及那些看似简单但一写就错的边界条件全部拆开讲清楚。无论你是刚开始刷搜索题的萌新还是已经会写 BFS 但想补上 DFS 短板的选手这篇文章应该都能给你一些新的理解角度。1. 迷宫问题为什么是理解DFS的最佳入口1.1 迷宫考的不是“走路”是状态空间先想一个问题所谓的走迷宫本质是什么从一个坐标点出发每走一步就是一次状态转移——当前位置坐标就是一个状态。整个迷宫里所有能站的格子合在一起就构成了一张“状态图”。DFS 在这个状态图上的行为说白了就是从当前状态出发挑一个没走过的邻居走过去走到死胡同就退回上一个状态再挑另一个邻居。这个描述听起来简单但它能解释很多直觉上的困惑。比如为什么 DFS 天然适合做“可达性”和“路径枚举”因为递归本身就是一种不撞南墙不回头的线性推进正好和“一条路走到黑、再回头选另一条路”的迷宫探索方式完全吻合。我在给初学者讲这个概念的时候喜欢用一个类比你进了一个迷宫但没有地图也没有手机你想看某一扇门后面到底能不能通到出口最笨的办法是什么就是推开门走进去一路往前走碰到岔路就选一条走到死胡同就原路退回岔路口再选另一条。这个“原路退回岔路口”的操作在递归里就是函数返回栈自动帮你完成的。DFS 能成为走迷宫问题的标准解法底层逻辑就在这里——它的天然形态和迷宫探索的物理过程是逐字对应的。1.2 竞赛里迷宫题的真实面貌算法竞赛中的走迷宫问题通常都有如下设定地图是一个 n 行 m 列的二维网格每个格子要么是空地用.或0表示要么是障碍物用#或1表示给定起点(sx, sy)和终点(ex, ey)每次移动只能走上下左右四个方向也有少数题允许八方向问法常见有这么几种判断起点能否到达终点输出一条从起点到终点的路径统计从起点到终点的所有可行路径数量在满足某些附加条件比如不能走回头路时的路径方案数。前两种问法用 DFS 和 BFS 都能做但 DFS 的代码往往更短、更直观第三种问法DFS 几乎就是唯一简单的选择——因为路径数量本质上要求“枚举所有可能”而枚举所有状态路径正是 DFS 递归回溯的看家本领BFS 虽然也能通过状态记录来做但复杂度会高很多代码也更绕。所以我的建议很明确DFS 走迷宫不是“BFS 的平替”也不是“最短路径的退而求其次”它是一种独立且关键的搜索思维方式。学好它你后面碰到的排列组合、子集生成、N皇后、连通性判断、拓扑排序乃至记忆化搜索都是在同一个思维框架上长出来的。2. 递归函数与状态设计先理清这一步再写代码2.1 dfs(x, y) 里的参数到底在传什么很多初学 DFS 的人第一个卡点就是这个递归函数的参数应该怎么定对于最基本的迷宫可达性问题参数只需要两个——当前所在的坐标。dfs(x, y)表示“我当前站在(x, y)这个格子上接下来我要尝试所有可能的方向寻找一条能到达终点的路”。这个函数在执行过程只需要回答一个问题从(x, y)出发在不走重复格子的前提下能不能到达终点于是代码骨架是这样的bool dfs(int x, int y) { if (x ex y ey) return true; // 走到终点了 visited[x][y] true; // 标记当前格子已访问 for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 || nx n || ny 0 || ny m) continue; // 出界跳过 if (visited[nx][ny]) continue; // 已经走过就跳过 if (maze[nx][ny] #) continue; // 障碍物跳过 if (dfs(nx, ny)) return true; // 子问题能到达终点当前也能 } return false; // 所有方向都试过了到不了 }这段代码看起来不难但有几个细节值得琢磨。第一为什么进入函数第一件事就判断终点而不是在扩展下一个节点时才判断因为这样写当起点和终点重合时也能直接返回true虽然这种情况在绝大多数迷宫题里不会出现但养成好习惯没坏处。第二标记visited[x][y] true的位置为什么放在方向遍历之前而不是之后因为在遍历方向之前我们已经站在这个点上了它的“已访问”状态必须从这一刻起生效否则四个方向的递归都会回到这个点造成无限循环递归栈直接爆炸。第三为什么递归返回true之后要立刻return true而不是继续循环因为我们只想知道是否“存在一条路径”找到一个就够了。只要子问题告诉我能走到终点就没有必要继续看别的方向了。2.2 方向数组的两个经典写法方向数组是走迷宫问题里的高频点写法基本固定但确实有人在这里翻车。最标准的是这样int dx[4] { -1, 1, 0, 0 }; int dy[4] { 0, 0, -1, 1 };四组对应四个方向上、下、左、右。你当然可以写成{0, 1, 0, -1}配{1, 0, -1, 0}之类的变体只要保证每次移动的位移量组合是合法的四个方向之一就行。判断越界有两种习惯// 写法一进入递归前先检查 if (nx 0 || nx n || ny 0 || ny m) continue; // 写法二在 dfs 开头统一检查 void dfs(int x, int y) { if (x 0 || x n || y 0 || y m) return; ... }我个人的习惯是写法一。原因很简单越界检查放在扩展邻居时做能让递归函数内部更干净不需要每次进入都做一层判断。而且对于后面要加的剪枝条件集中在一个地方控制“哪些邻居可以走”是更符合直觉的。不过写法二也完全没有问题尤其是当你需要处理“移动步数超过 K”、“走了某些格子会掉血”这类带附加条件的迷宫时把合法性判断统一收敛在函数开头反而更好维护。两种都要会写看场景切换。2.3 用一个小迷宫手推一遍 DFS 的执行过程光看代码很难建立递归调用的画面感。我们用下面这个 3x3 的小迷宫走一遍S . . # # . . . ES是起点(0,0)E是终点(2,2)#是不能走的墙。执行dfs(0, 0)后会发生什么dfs(0,0)标记(0,0)为已访问依次检查四个方向。上越界下是(1,0)是墙左越界右是(0,1)是空地于是进入dfs(0,1)。dfs(0,1)标记后上越界下是(1,1)是墙左是(0,0)已访问右是(0,2)是空地进入dfs(0,2)。dfs(0,2)标记后上越界下是(1,2)是墙左是(0,1)已访问右越界。四个方向都不满足返回false。回到dfs(0,1)四方向已全部试完返回false。回到dfs(0,0)右方向的结果是false继续尝试下方向。下是(1,0)是墙跳过。此时四个方向都试完了返回false等等这跟直觉不符。我们明明可以看出有一条路径(0,0) - (0,1) - (0,2)走不通但真正能走通的路径是(0,0) - (0,1) - (0,2)这一行本身就是死路正确答案应该是从(0,0)往下绕但上面地图(1,0)和(1,1)都是墙这个迷宫其实根本走不通。是我例子举得不合适换个 4x4 的例子推演。S . . . # # # . . . . . # # # E这个迷宫里唯一路径是上面绕不过去的实际得从(0,0)向右走到(0,3)再向下到(3,3)。过程是这样的dfs(0,0)标记右进(0,1)。dfs(0,1)标记右进(0,2)。dfs(0,2)标记右进(0,3)。dfs(0,3)标记下是(1,3)空地进入。dfs(1,3)标记「已访问」。此时它下边(2,3)是空地继续。dfs(2,3)标记上(1,3)已访问下(3,3)是终点触发终止条件返回true。一路回溯每次if (dfs(nx, ny)) return true;都成立整个函数返回true。这个推演过程很重要它揭示了 DFS 的一个核心特征它是深度优先的会沿一条分支一路走到黑只有当整条分支都返回false时才会回到上次的岔路口尝试下一条。这个“先深后回”的顺序决定了你在调试递归问题时长什么样的问题也决定了为什么可以用一个栈来模拟递归不过手动栈写法在竞赛里确实用得少因为递归写法更直白。3. 从“能不能到”到“怎么走”三种典型问法的代码演进3.1 基础版判断起点到终点是否可达第 2 节里展示的其实就是可达性判断的完整代码。这个版本的关键是访问标记一旦打上就永远不回退也就是不入循环。为什么不必回退因为我们要回答的问题只是“有没有一条路径”而不是“走法有哪些”。对于连通性判断一个格子只要走过一次再次回到它是没有意义的——既然之前已经从这个格子出发尝试过所有可能的方向那结果已经确定了再走一遍是纯粹浪费。这么设计的好处是每个格子最多被进入一次时间复杂度严格为 O(n*m)。这在竞赛中非常重要很多选手写 DFS 时没想清楚这一点访问标记来回撤销一次搜索的复杂度直接变成指数级地图稍大一点就 TLE。3.2 升级版输出完整路径如果要输出一条路径做法是维护一个容器记录当前走过的轨迹。在 C 里通常用一个vectorpairint,int path;或者两个一维数组px[], py[]。当递归进入某个格子时把坐标压入容器当递归从该格子返回并发现走不通时把它弹出去。一旦到达终点就把当前容器里的记录输出。这个“压入-弹出”的过程就是我们常说的回溯。它的本质是递归深入时和返回时手动维护的轨迹容器必须与递归栈的当前层级保持一致。压入和弹出的时机如果错位输出的路径就会多出格子或者丢格子。这里有个特别容易踩的坑做可达性判断时访问标记不加回溯但做路径输出或方案统计时访问标记必须回溯。我见过很多选手在这两种场景间切换时忘记把visited的恢复逻辑加上或者删掉结果要么路径数量少算很多要么代码死循环。路径输出的关键片段大概是这样的vectorpairint, int path; bool dfs(int x, int y) { if (x ex y ey) { path.push_back({x, y}); for (auto p : path) cout ( p.first , p.second ) ; cout endl; path.pop_back(); return true; // 只输出一条就返回 } visited[x][y] true; path.push_back({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 (visited[nx][ny] || maze[nx][ny] #) continue; if (dfs(nx, ny)) return true; } path.pop_back(); visited[x][y] false; // 回溯恢复 return false; }注意这里的两个尾部操作顺序很重要path.pop_back()和visited[x][y] false都要在函数返回之前执行。含义是当前格子的所有方向都试完了既没有走到终点也没有任何子递归能返回true那么这个格子对于当前这条探索路径来说已经没有用了退出时把它的痕迹一并清除。这样下一轮走别的路径时这个格子还能被重新访问。3.3 进阶版统计可行路径数“统计从起点到终点的不同路径数量”是 DFS 迷宫问题里最经典的进阶问法。这时候我们就不能“找到一条就返回”了而是必须把整棵搜索树完整跑一遍每次抵达终点就累计一次int ans 0; void dfs(int x, int y) { if (x ex y ey) { ans; return; } visited[x][y] true; 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 (visited[nx][ny] || maze[nx][ny] #) continue; dfs(nx, ny); } visited[x][y] false; }这个版本最核心的一点就是函数末尾的visited[x][y] false这一行决定了它是“枚举所有路径”而不是“判断可达性”。你可以理解为每个格子我只占用的当前这条探索路线路线因为走不通或者到达终点而结束后这个格子应该被“释放”让其他路线可以再次踩过。这里需要给初学者一个提醒这种不带任何剪枝的裸 DFS路径数量上去之后复杂度是爆炸的。在一个 5x5 的完全开放地图里路径数量就可能达到数万条10x10 就基本跑不完了。所以这类题目通常出现在数据范围很小比如 n, m≤8的场合或者必须配合后面要说的剪枝和记忆化技巧。4. 效率瓶颈与优化思路DFS 不是只能“莽”4.1 剪枝到底在剪什么剪枝这个词听着高深其实就是提前判定某条分支不可能产生正确答案从而省掉整棵子树的搜索。在迷宫问题里最常用的剪枝有这几类。第一是边界剪枝。方向越界的邻居根本不用进去这其实已经写在continue里了。很多初学的人会忘记或写错这个判断导致递归访问到maze[-1][2]这类非法坐标。在大多数在线评测系统里这是未定义行为轻则答案错误重则段错误或运行时异常。第二是障碍物剪枝。目标格子是#就不走。这个也是基础操作难点在于把障碍物和已访问的判断合在一起写的时候不要因为短路求值顺序出错导致漏判或双重判断。第三是奇偶性剪枝这也是竞赛里很妙的一招。如果从起点到终点的曼哈顿距离是奇数而当前已经走的步数和剩余可走步数的奇偶性不匹配就可以提前结束。比如题目限定“必须在多少步以内到达终点”那么根据曼哈顿距离的奇偶性可以直接砍掉大量分支。虽然这不是迷宫场景最常见的技巧但它体现了剪枝的核心思想——在进入递归之前用数学性质判断这条路径还有没有希望。4.2 记忆化加法变乘法假设问题是“从起点到终点有多少条可行路径”而且地图较大裸 DFS 会超时。这时候可以考虑记忆化搜索开一个dp[x][y]数组表示从(x, y)出发到达终点的路径数。逻辑是如果(x, y)是终点返回 1如果dp[x][y]已经算过直接返回否则dp[x][y]等于四个方向能走的格子各自的dp值之和。这个技巧的本质是把 DFS 从“树的递归遍历”升级为“动态规划 递推”每个格子的值只计算一次。细节上要注意无障碍、可重复走的地图是不能直接这样记忆化的因为路径数可能发散它要求状态之间存在严格的转移依赖也就是每个格子最多被处理一次。标准的迷宫题目每个格子最多走一次天然满足这个条件所以记忆化是安全的。这里我补充一个很多人忽略的判断记忆化搜索能成立前提是“从(x, y)出发的搜索结果只和当前坐标有关和来时的路径无关”。如果题目里加入“不能连续两次走同一个方向”“踩过某些格子后状态变化”这类约束简单记忆化会出错。这时候你需要把状态扩展成dp[x][y][state]状态里带上影响后续决策的所有信息。4.3 什么时候改换 BFSDFS 并不是所有迷宫题的最优解这点我反复强调过因为确实有太多人拿着 DFS 硬解最短路径问题然后抱怨 TLE。最短路径问题请用 BFS。原因很简单BFS 首次到达终点的层数一定是最少的而 DFS 在无剪枝状态下可能把整个地图翻个底朝天才好不容易走到终点而且它找到的第一条路径完全不能保证最短。两者应用场景我用一个表格总结一下问题类型推荐算法原因判断是否可达DFS 或 BFS 均可两者都能做到DFS 代码短输出任意一条路径DFS 或 BFS 均可DFS 回溯直观BFS 需额外记录前驱输出最短路径步数BFSBFS 层级即最短步数统计可行路径数量DFS记忆化BFS 状态记录复杂带状态压缩的连通性DFS 状态标记搜索树形态天然适合判断连通块个数DFS 或 BFS 均可遍历时逐个标记即可这其实是一种“算法选型”意识。搜索题不是上来就选一个算法硬套而是先读题判断问题的本质是“可达性 / 最短性 / 计数型”再去选合适工具。很多选手刷了几百道题还在点搜索技能点但从来不总结“这道题为什么用 DFS 而不是 BFS”这是很可惜的。5. 经典变式传送门、多出口与状态扩展5.1 带传送门的迷宫搜索状态要升级竞赛里经常出现“迷宫里有传送门恰好在一个格子可以瞬间传到另一个指定格子”的设定。这类问题的关键不在 DFS 的框架本身而在于状态定义要跟着变。如果每个传送门只能用一次那么坐标本身不足以唯一描述一个状态你还得记录每个传送门的使用情况状态就变成(x, y, mask)其中mask是一个二进制数第 i 位表示第 i 个传送门是否已经被用过。这是典型的“状态压缩 DFS”。如果传送门无使用次数限制问题反而简单直接把传送目标格子也作为该格子的邻接节点即可。在扩展四方向的时候加一条if (teleport[x][y] ! -1) { dfs(teleport[x][y], y); // 假设 teleport[x][y] 返回目标 x 坐标 }注意这要小心陷入“原地传送”或“来回传送”的死循环。处理方案仍然是访问标记或者在状态定义中加入“最后一次传送时间”来防止连续多次触发传送。这种细节在实际题目里经常成为区分 AC 和 WA 的分界线。5.2 多起点多终点加一层虚拟节点有些题不给你单个起点而是说“可以从任意标记为 S 的点出发到达任意标记为 E 的点”。遇到这种情况最简单的做法不是对每个起点分别 DFS而是在进入搜索前把所有起点统一处理成同一种状态。具体做法直接对每个起点依次执行 DFS只要有任何一个返回true就结束或者引入一个虚拟的超级起点和所有实际起点之间连一条“零代价边”一次 DFS 就能覆盖所有起点。后者在代码实现上更整洁尤其在你想对“是否存在一条从入口集合到出口集合的路径”做统一判断时特别有用。多终点也很简单递归出口条件从“是否等于终点坐标”改成“当前格子是否在出口集合中”。这种逻辑的统一处理能让代码变得更可读也避免复制粘贴产生低级错误。5.3 附加步数限制与带权格子有时题目会加“要求路径长度不能超过 K”或“经过某些格子会扣血”。处理思路都是一致的把限制条件编码进递归参数中。例如步数限制可以把函数签名改为dfs(x, y, step)当step K时直接返回到达终点且step K时才更新答案。例如血量限制可以把hp作为递归参数踩到扣血格子就减少hphp 0时剪枝。这类问题的共同特征是状态必须包含影响未来决策的所有累积量。这也是我在 4.2 节强调的“状态设计意识”——不要把 DFS 简单理解成dfs(x, y)它本质上是一个关于状态的递推函数参数列表决定了它能表达多少种状态组合。6. 实战调试心得我在这类题上踩过的坑6.1 访问标记的三种常见错误走迷宫题我是真踩过不少坑其中访问标记相关的错误占了七成。我这里总结三种典型第一种标记了不恢复。在统计路径数量时visited[x][y] false如果没写那第一条路径走完后起点往外的很多格子仍然处于“已访问”状态后面的路径根本走不出去。答案会非常离谱地偏小。调试方法就是打印每次到达终点时的路径长度如果越走越短甚至完全不输出那基本就是标记没恢复。第二种恢复了不该恢复的标记。在可达性判断和记忆化搜索的场景中visited是全局共享的“这个格子已经被完全搜索过”的标志一旦恢复就会导致同一个子问题被重复计算复杂度从 O(n*m) 涨到指数级。这种 bug 因为不爆栈、不超时到肉眼能看出来的程度经常被忽略直到大数据范围 TLE 才发现。第三种标记时机不对。标记放在dfs函数返回值后面才打会导致当前格子可能被自身四条方向的子递归重复进入。虽然迷宫有边界限制但这种错误在特定地图形状下会出现死循环表现为程序疯跑不停、栈溢出。判断方法很简单在dfs入口打印当前坐标如果同一个坐标连续出现多次而你又没有合法的环结构那大概率就是标记时机问题。6.2 用“打印递归深度”调试我强烈建议在入门阶段养成一个调试习惯在 DFS 函数里打印当前坐标和递归深度。像这样void dfs(int x, int y, int depth) { cout string(depth * 2, ) ( x , y ) depth depth endl; ... }输出效果就是一棵直观的递归树。你一眼就能看出某个分支是否重复访问同一个点递归是否正确地回溯depth 是否递减有没有哪个方向的搜索明显超出预期。这比你对着编辑器断点一步步跟要高效得多尤其在地图规模比较大的时候。竞赛环境里 GDB 调试不总是方便而这种打印法在任何环境都能用是性价比最高的调试手段。6.3 输入输出和坐标习惯的一点点建议最后分享两个个人习惯。一是坐标统一用 0-based 还是 1-based在代码开头想清楚。竞赛题输入给出的坐标常常是 1-based比如起点是(1,1)而数组下标是 0-based如果不做转换读入后立刻--是常见做法。千万别一半代码用 0-based一半用 1-based那真是无解的灾难。二是地图尽量用字符串数组。C 里vectorstring maze;比vectorvectorchar更简洁逻辑上也更容易理解和调试maze[x][y] #用起来跟二维字符数组一样直观。这个纯属风格偏好但对于竞赛码速来说能少打几个字符都是优势。7. 从迷宫出发DFS 思维能走多远迷宫问题只是一个起点但它帮你建立起来的几件事——状态设计、递归深入、回溯时机、剪枝意识、记忆化的适用条件——是你后面解决更复杂搜索问题的共同地基。比如 N 皇后问题它就是一个把棋盘行号当递归层数的 DFS数独求解是在每个空格枚举 1 到 9 并递归检查合法性的 DFS子集生成和排列组合更是 DFS 的经典入门应用状态压缩 DP 里的很多状态转移本质上也带有 DFS 记忆化搜索的影子。所以当你把迷宫题刷透后面遇到这些题时要做的事情其实是同一套定义清楚状态、设计好递归出口、想清楚访问标记何时恢复、考虑剪枝和记忆化的适用性。思路通了代码只是最后落地的那一步。我自己在刷题的时候特别喜欢把每道搜索题都问自己三个问题状态是什么出口在哪回溯什么如果三个问题都能在动手前答清楚代码基本不会错到哪里去。希望你也能把这三个问题变成自己的默认流程那这篇关于 DFS 走迷宫的文章就算真正帮到你了。