备战蓝桥杯的C选手十个里有八个在DFS迷宫题上栽过跟头。不是不会写递归也不是看不懂回溯而是栽在一些看起来完全不起眼的“模板细节”上方向数组写错了半个下标、访问标记提前了一行、读入字符时被换行符坑了一道。每次在OJ上跑出来WA或者RE又死活查不出原因的时候真的会怀疑人生。这篇东西就是冲着“手写DFS迷宫模板”去的专门拆解小白最容易踩的3个致命坑。我会把每个坑的错误现场、根因、修复方式、以及对应的调试验证过程都写出来最后给出一份可以直接抄的完整模板。适合正在备赛蓝桥杯C组、或者刚学完DFS却总在迷宫题上挂掉的选手也适合拿模板背完却不理解为什么这么写的同学。只要你还在“按模板写代码”这篇就能帮你少走很多弯路。1. 为什么“会写DFS模板”和“能AC迷宫题”完全是两码事先说一个很扎心的现象。很多同学手里都有一份“DFS迷宫模板”大概长这样一个dfs()函数、一个vis[][]数组、一个方向数组、一个边界判断然后递归进去回溯出来。背得滚瓜烂熟上课也能默写出来。但一上蓝桥杯的赛场遇到稍微变个花样的迷宫题就开始翻车。翻车的原因往往不是“不懂DFS”而是模板里的那些细节从来就没真正搞明白过。为什么背熟了模板还会错因为模板是“死的”题目是“活的”。一份模板要能在考场上稳得住至少得回答清楚这几个问题方向数组为什么要这么写dx/dy的四个组合到底代表什么vis数组到底是在什么时候标记的是在进入递归之前还是在扩展邻居的时候回溯时需不需要把vis恢复成未访问什么情况下必须恢复什么情况下绝对不能恢复边界条件是0 x n还是1 x n这取决于你读入地图时的下标从几开始。处理字符迷宫时cin ch和scanf( %c, ch)有什么本质区别这些问题看起来都“很小”但每一个都可能让你的程序从“AC”变成“WA”或“RE”。而且最麻烦的是有一些错误并不会直接崩溃而是会静悄悄地给出一个错误答案让你查半天都查不出来。我在备赛期间就帮同学排查过大量类似的问题其中三个坑出现的频率最高几乎可以称为“小白三连”。2. 致命坑一方向数组与坐标映射的“看似正确实则越界”2.1 错误现场答案错得莫名其妙甚至干脆RE先说第一个坑也是新手写迷宫DFS时第一个就会碰上的坑方向数组。大多数模板里会这么写int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1};这套写法表示四个方向分别是“下、上、右、左”配合x表示行、y表示列的约定。看起来没毛病但问题往往出在“你以为你写的是这个实际上你写的是另一个”。常见的错误版本包括但不限于// 错误示例1dx和dy配错了位置 int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; // 这写法本身没错但你要清楚它代表“右、左、下、上” // 错误示例2写成了四个方向但只覆盖了三个方向 int dx[4] {1, 0, 0, -1}; int dy[4] {0, 1, -1, 0}; // 看起来覆盖了实际组合是{1,0},{0,1},{0,-1},{-1,0}这四种组合分别是“下、右、左、上”其实覆盖全了。但如果你在循环里写的是for (int i 0; i 4; i)而方向数组只给了三个值那就直接从数组越界开始崩。更隐蔽的是在二维数组的坐标使用上。数组[x][y]中x是行下标第一维y是列下标第二维。所以x的变化方向对应“上下”y的变化方向对应“左右”。但很多同学写着写着就把x当成横坐标、y当成纵坐标于是// 这样写会让你在“左右移动”时改变的是行而不是列 int nx x dir[i][0]; // 本该是y int ny y dir[i][1]; // 本该是x结果是什么地图的访问范围完全错乱明明眼前有路程序却撞墙甚至直接跳到地图外面造成RE。2.2 根因分析坐标维度的抽象混乱要说清楚这个坑得先把坐标系彻底捋一遍。在迷宫题里我们通常用一个二维字符数组存地图char maze[105][105];maze[x][y]的语义是“第x行、第y列的格子”。如果你把整个迷宫想象成一张表格那么x是从上到下的行号对应“纵向”。y是从左到右的列号对应“横向”。所以当你从当前格子(x, y)出发想去右边的格子正确的操作是int nx x; // 行号不变 int ny y 1; // 列号加1当你想去下面的格子正确操作是int nx x 1; // 行号加1 int ny y; // 列号不变只要把这两组关系理清楚方向数组就不会写反。我建议新手在写之前先在自己的草稿纸上画一个3x3的格子把每个格子的坐标标出来然后再对着格子的上下左右写方向数组。这样写出来的代码往往一眼就能看出问题。2.3 修复方案与防御性写法最稳妥的写法是把方向数组和坐标更新分开写并且在注释里标明每个方向int dx[4] {1, -1, 0, 0}; // 下、上、右、左 int dy[4] {0, 0, 1, -1}; // 有些同学喜欢用pair或者结构体也可以 // pairint, int dir[4] {{1,0},{-1,0},{0,1},{0,-1}}; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 然后判断边界 }还要养成一个习惯在DFS函数开头加一个“合法性检查”而不是在扩展时才判断。这样即使方向数组写错了程序最多是提前返回不至于越界崩溃void dfs(int x, int y) { if (x 0 || x n || y 0 || y m) return; if (maze[x][y] #) return; // 墙 if (vis[x][y]) return; vis[x][y] true; // 继续递归... }把边界判断放在函数开头整个代码的可读性和健壮性都会好很多这也是很多比赛选手推荐的方式。3. 致命坑二vis标记的时机错一个位置结果差十万八千里3.1 错误现场要么死循环要么漏路径如果说方向数组是“第一道坎”那么vis标记的时机就是“第二道坎”而且这道坎更隐蔽。vis数组的作用是防止DFS反复走进同一个格子而陷入死循环。但“什么时候标记”这个问题不同写法的后果天差地别。我先展示两种常见写法。写法A在进入DFS时标记推荐void dfs(int x, int y) { vis[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 !vis[nx][ny] maze[nx][ny] ! #) { dfs(nx, ny); } } }写法B在扩展时标记新手最爱犯导致重复进入void dfs(int x, int y) { // 没有一进函数就标记 // 处理当前格子... for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; vis[nx][ny] true; // 在邻居节点标记 if (边界 !vis[nx][ny] maze[nx][ny] ! #) { dfs(nx, ny); } } }写法B的问题很明显你在if判断之前就把vis[nx][ny]设成了true然后紧接着又在条件里判断!vis[nx][ny]这时它已经是true了所以这个格子永远不会被递归进去。反过来如果有人在if判断里写的是if (边界 maze[nx][ny] ! #) { vis[nx][ny] true; dfs(nx, ny); }那就变成了“先判断再标记”看起来对但如果同一层循环里有两个方向都通向同一个格子这个格子会被重复入队递归可能造成重复计算甚至死循环。更麻烦的是如果某条路径在递归中改了这个格子的访问状态你很难追踪是哪里出的问题。3.2 根因分析标记时机决定的是“路径去重”还是“状态回溯”要理解vis标记时机的本质得先分清两种不同的需求。第一类需求只要判断“从起点能不能走到终点”或者“能到达的格子有哪些”。这种需求下每个格子只需要访问一次不需要撤销标记。因为你的目的是“覆盖所有可达格子”而不是“枚举所有路径”。此时vis标记应该在“格子第一次被确认可以访问”时就设上之后不会再撤销。第二类需求要统计“从起点到终点一共有多少条不同路径”或者要“打印出每一条路径”。这种需求下你不能让一个格子永久处于已访问状态因为不同路径允许经过同一个格子。这时vis不是“去重工具”而是“当前路径上已占用格子的标记”。递归返回时必须撤销标记也就是回溯。所以“回溯时到底要不要把vis[x][y]恢复成false”不是看模板而是看题目问的是什么。很多同学把两种混在一起结果就是第一种需求下加了回溯撤销导致一个格子被反复走程序超时。第二种需求下没加回溯撤销导致路径数量被严重少算。3.3 修复方案与判断标准我自己的判断标准很简单如果DFS的递归过程中你希望两个不同的搜索分支能共享同一个格子那这个格子的vis必须支持“撤销”如果不希望那就不要撤销。具体落地时可以这样处理如果是“可达性/连通块”类问题采用“进入即标记且不回溯”void dfs(int x, int y) { vis[x][y] true; // 扩展四个方向 for (...) { if (合法 !vis[nx][ny]) { dfs(nx, ny); } } // 不需要vis[x][y] false; }如果是“路径计数/打印路径”类问题采用“进入即标记返回前回溯”void dfs(int x, int y) { if (x ex y ey) { ans; return; } vis[x][y] true; for (...) { if (合法 !vis[nx][ny]) { dfs(nx, ny); } } vis[x][y] false; // 回溯撤销当前格子的占用状态 }这两段代码的区别只在最后一行但适用场景完全不同。建议你把这两套写法都吃透比赛时根据题目要求选择而不是死背一份模板硬套。4. 致命坑三输入格式与边界条件的“经典阴间配置”4.1 错误现场WA得毫无头绪样例却能过第三个坑不是DFS本身的问题而是“地图都读错了后面全是白干”。蓝桥杯的迷宫题输入格式非常喜欢挖坑。常见的坑有几种第一种字符之间可能没有空格直接一串字符串。5 5 S#### ..... ##### ..... ####E这种没有空格的字符串如果你用cin char循环读其实也能读因为cin 会自动跳过空格和换行把每个字符依次喂进来。但如果你用scanf(%c, ch)就要小心了%c不会跳过空白字符它会连换行符一起读进来。于是你辛辛苦苦读进来的地图里混进了一堆\n后面判断maze[x][y] #时永远匹配不上因为maze里存的是回车。解决办法是用scanf( %c, ch)在%c前面加一个空格告诉scanf先跳过所有空白字符再读一个字符。或者干脆用cin 它天生会跳过空白。第二种读入时下标从1开始还是从0开始定了就别改。很多同学在写边界条件时今天用x n明天用x n或者读地图时从i 1开始但边界判断用的是0 x n导致第一行和第一列永远处于“不可达”状态。我建议的做法是下标统一从1开始读边界判断也统一从1到n这样最符合“第几行第几列”的自然语言直觉也能避免很多边界混淆。int n, m; cin n m; for (int i 1; i n; i) { cin (maze[i] 1); // 如果迷宫是字符串就把第0列留出来从第1列开始存 }注意这句(maze[i] 1)意思是把字符串从下标为1的位置开始存。前提是maze是二维char数组且每行长度够大。这样maze[x][y]里的x范围就是1~n、y范围就是1~m。第三种起点终点藏在字符里很多人只判断了墙忘了判断起点终点。蓝桥杯的迷宫题起终点常用S和E表示。有些同学DFS扩展时只判断了maze[nx][ny] ! #结果把E当成墙直接跳过导致永远找不到终点。正确做法是只要不是墙就能走起点终点只是普通可通行格子。if (maze[nx][ny] ! #) { // 可通行不管是S、E还是.都可以走 }或者更稳妥把S和E在读入后统一改成.然后在主函数里额外记录起终点坐标。这样DFS内部逻辑就只需要关心“这里是墙还是可以走”不用纠结字符含义。4.2 根因分析你以为在读地图其实在读了个寂寞为什么输入格式能坑这么多小白因为很多人把cin和scanf的空白处理机制完全搞混了。cin 在处理char、int、string时默认会跳过所有空白字符空格、换行、制表符。所以cin ch连续读字符时绝对不会读到换行符。scanf就不一样。scanf(%c, ch)会把换行符、空格原封不动读进来。很多人用scanf读整数没问题因为%d也会跳过空白但一到%c就翻车。所以如果你习惯用scanf读字符迷宫千万记得%c前面加空格scanf( %c, ch);如果你用cin读整行字符串需要注意getline会读取包括换行符在内的整行内容。在读完整数后面紧跟getline时需要先把换行符“吃掉”int n, m; cin n m; // 读完后末尾留下一个换行符 getchar(); // 将这个换行符消费掉 for (int i 1; i n; i) { cin.getline(maze[i] 1, maxn); // 这样再读就不会读到一个空行了 }4.3 修复方案与边界自检清单分享一个我自己比赛时读迷宫题的固定套路照着写基本不会出问题const int MAXN 105; char maze[MAXN][MAXN]; bool vis[MAXN][MAXN]; int n, m, sx, sy, ex, ey; void findStartEnd() { for (int i 1; i n; i) { for (int j 1; j m; j) { if (maze[i][j] S) sx i, sy j, maze[i][j] .; if (maze[i][j] E) ex i, ey j, maze[i][j] .; } } } int main() { cin n m; for (int i 1; i n; i) { cin (maze[i] 1); // 下标从1开始 } findStartEnd(); // 提前处理起点终点DFS里只关心墙和非墙 // 调用dfs(sx, sy)检查vis[ex][ey] return 0; }写完后边界条件统一是if (nx 1 || nx n || ny 1 || ny m) continue; if (maze[nx][ny] #) continue; if (vis[nx][ny]) continue;这个“三连continue”把所有非法情况都挡在递归之外逻辑非常清晰。5. 一份能直接抄作业的DFS迷宫模板含三种变体把前面三个坑都排掉之后下面给出一份我自己现在还在用的模板。它不花哨但足够稳基本覆盖了蓝桥杯常见DFS迷宫题的三种玩法问可达性、统计路径条数、打印路径。5.1 基础模板判断从起点能否到达终点#include bits/stdc.h using namespace std; const int MAXN 105; char maze[MAXN][MAXN]; bool vis[MAXN][MAXN]; int n, m; int sx, sy, ex, ey; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; void dfs(int x, int y) { // 进入即标记 vis[x][y] true; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 边界 墙 访问状态三个条件一个都不能少 if (nx 1 || nx n || ny 1 || ny m) continue; if (maze[nx][ny] #) continue; if (vis[nx][ny]) continue; dfs(nx, ny); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; for (int i 1; i n; i) { cin (maze[i] 1); } for (int i 1; i n; i) { for (int j 1; j m; j) { if (maze[i][j] S) { sx i; sy j; maze[i][j] .; } if (maze[i][j] E) { ex i; ey j; maze[i][j] .; } } } dfs(sx, sy); if (vis[ex][ey]) cout Yes endl; else cout No endl; return 0; }这份模板的核心是不管DFS内部怎么递归最终只需要看终点格子有没有被打上vis标记。因为vis标记意味着“这个格子已经被访问并确认可通行”。如果终点被访问到了说明起点和终点连通。5.2 变体一统计起点到终点的路径条数这个变体需要用到回溯因为同一条路径经过的格子集合是固定的但不同路径之间可以共享格子。如果不回溯DFS会认为某个格子已经被占用导致路径计数偏少。int ans 0; void dfsCount(int x, int y) { if (x ex y ey) { ans; return; } vis[x][y] true; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 1 || nx n || ny 1 || ny m) continue; if (maze[nx][ny] #) continue; if (vis[nx][ny]) continue; dfsCount(nx, ny); } vis[x][y] false; // 关键回溯撤销标记 }有两点要注意一是这个写法在到达终点时直接返回没有把终点标记为已访问。这样如果有多条路径以不同顺序经过终点同层格子的前驱依然能正常统计。二是递归深度不要太大。如果迷宫是100x100统计所有路径条数会非常爆炸大概率超时。所以路径计数题通常数据范围很小或者是要求“方案数模某个数”才会用DFS。5.3 变体二打印一条可行路径打印路径需要在DFS过程中记录走过的坐标序列。最简单的做法是用一个数组或vectorpairint,int来维护“当前路径”。vectorpairint, int path; bool found false; void dfsPath(int x, int y) { if (found) return; // 已找到一条路径直接剪枝 if (x ex y ey) { found true; for (auto [px, py] : path) { cout ( px , py ) - ; } cout ( x , y ) endl; return; } vis[x][y] true; path.push_back({x, y}); for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 1 || nx n || ny 1 || ny m) continue; if (maze[nx][ny] #) continue; if (vis[nx][ny]) continue; dfsPath(nx, ny); if (found) return; // 路径已找到不再搜索其他分支 } path.pop_back(); // 回溯从路径中移除当前格子 vis[x][y] false; // 回溯撤销标记 }注意path.pop_back();和vis[x][y] false;必须成对出现。前者负责维护路径序列后者保证其他路径分支也能走到这个格子。这个模板在实际比赛里非常实用尤其是“输出一条从S到E的路径”这种题很多同学只会判断可达性一要求输出路径就懵了。6. 排查顺序与调试技巧用完例造数据别指望样例一次过6.1 提交WA/RE之前的“一分钟自检清单”很多同学在OJ上WA了之后第一反应是打开代码逐行看效率很低。我建议按下面这个顺序排查一分钟内能定位大部分问题。第一步检查输入格式。先用最朴素的方式把你的地图打印出来for (int i 1; i n; i) { cout (maze[i] 1) endl; }如果打印出来发现第一行是空行或者字符错位那问题出在读入环节而不是DFS。此时检查你是不是用scanf(%c)读了字符、或者getline吃掉了换行。第二步检查起点和终点是否被正确记录。在调用DFS之前打印一下sx, sy, ex, eycout S: sx sy endl; cout E: ex ey endl;如果S和E都没有被识别出来多半是地图读入的问题或者你是否忘了把字符S和E处理好。第三步检查vis标记的时机。如果程序出现无限递归导致栈溢出RE或者运行时间长得离谱TLE先看vis标记是不是在进入递归之前设置的。如果DFS在扩展邻居时才标记而且标记时机不对很容易造成重复访问。一个很经典的调试技巧在DFS函数开头加一行输出观察坐标是否有重复void dfs(int x, int y) { // cout dfs: x y endl; ... }把注释去掉跑一个小样例如果同样的坐标被输出多次那vis标记肯定有问题。6.2 自己造数据的能力才是决定比赛上限的关键蓝桥杯的样例往往很弱只靠样例AC就上考场大概率是要挂的。我个人的习惯是写完迷宫DFS后一定会自己造几组边界用例来测。最值得测的几组第一组刚好2行2列的最小迷宫。2 2 S. .E第二组起点就是终点。2 2 SE ..第三组完全被墙挡住没有通路。3 3 S## ### ##E第四组横着一条直线。1 5 S...E注意有些题目会故意把n1或m1的情况混进来。如果边界条件写得不严谨这种数据分分钟WA。比如上面这组1 5如果DFS里的方向数组仍然遍历四个方向那“上”“下”两个方向会因为越界被continue掉只有“左”“右”能用其实没问题。但如果你边界判断写的是nx n而不是nx n的严格大于就可能出现访问到s[1][-1]这种非法下标。自己造数据还有一个好处能顺便验证你对“题意的理解”是不是对的。有时候跑出来答案和你手算的不一致不是代码问题而是你根本没读懂题目想让你输出什么。6.3 最后再分享一个我常用的“递归可视化”调试法DFS很难调试因为它是一个递归过程普通的断点调试不好用。我自己最常用的方法是做一个缩进输出把递归过程“可视化”。void dfs(int x, int y, int depth) { // 输出当前访问状态 for (int i 0; i depth; i) cout ; cout ( x , y ) endl; vis[x][y] true; for (...) { ... dfs(nx, ny, depth 1); } vis[x][y] false; }运行输出会呈现一个树状结构一眼就能看出DFS每一步走到了哪里、哪些分支提前返回了、哪些格子被重复访问了。这个方法在调试路径统计和输出路径的题目时特别管用比对着看不出来问题的代码要高效得多。我现在写迷宫DFS已经完全不怕踩坑了。不是因为记得住模板而是因为每次踩坑后都顺手把“为什么错”刻在脑子里方向数组不对先看坐标维度vis出了问题先想清楚到底要不要回溯读入出了问题先打印地图。这些习惯一养成手写DFS就不再是玄学而是一件非常稳的事情。