【蓝桥杯/算法】DFS 深度优先搜索：万能模板与避坑指南（附两大核心题型）

DFS（深度优先搜索）做题步骤与万能模板

DFS 是蓝桥杯和算法竞赛中的绝对核心。很多初学者容易晕头转向，其实只要在写代码前问自己一个问题：这道题是“找所有路径（排列/迷宫）”，还是“找连通块（涂色/数岛屿）”？

注： 除了上述两类，DFS 还常用于树/图的遍历（无需回溯）以及子集/组合问题（需要回溯）。但万变不离其宗，核心都是基于“是否撤销现场”来划分的。

一、 第一步：30 秒判断题型

二、 路径型 / 选择型 DFS 模板

特征：必须“恢复现场”（回溯），因为要尝试所有分支。

#include<iostream>usingnamespacestd;intn,m;intans=0;intvis[105];// 一维：标记数字是否用过；二维地图则用 vis[105][105]voiddfs(intstep){// 1. 终止条件（到达目的地，或者选完了所有数）if(step>n){// 或者 (x == endX && y == endY)ans++;return;}// 2. 扩展（遍历所有可能的选择）for(inti=1;i<=n;i++){// 3. 合法性判断if(!vis[i]){// 4. 标记当前状态vis[i]=1;// 5. 递归下一层dfs(step+1);// 6. 回溯：恢复现场（核心！）vis[i]=0;}}}intmain(){cin>>n;dfs(1);// 从第一步开始cout<<ans<<endl;return0;}

补充：二维迷宫求路径数

// 二维迷宫路径型（求方案数）intsx,sy,ex,ey;// 起点和终点intvis[105][105];intdx[4]={0,0,1,-1};intdy[4]={1,-1,0,0};voiddfs_maze(intx,inty){if(x==ex&&y==ey){ans++;// 到达终点，方案数+1return;}for(inti=0;i<4;i++){intnx=x+dx[i],ny=y+dy[i];// 不越界 且 不是障碍 且 没走过if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&map[nx][ny]==0&&!vis[nx][ny]){vis[nx][ny]=1;// 标记dfs_maze(nx,ny);// 递归vis[nx][ny]=0;// 回溯}}}

三、 连通块型 DFS 模板

特征：一旦走到某个格子，就把它彻底同化，绝不回头。

#include<iostream>usingnamespacestd;intn,m,ans=0;charmap[105][105];intdx[4]={0,0,1,-1};// 四方向intdy[4]={1,-1,0,0};// 八方向：// int dx[8] = {-1,-1,-1,0,0,1,1,1};// int dy[8] = {-1,0,1,-1,1,-1,0,1};voiddfs(intx,inty){// 1. 标记当前格子（直接改地图，永久标记，不回溯）map[x][y]='.';// 2. 扩展方向for(inti=0;i<4;i++){intnx=x+dx[i];intny=y+dy[i];// 3. 合法性判断：不越界、且是目标地形（如 'W'）if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&map[nx][ny]=='W'){// 4. 递归（不需要回溯）dfs(nx,ny);}}}intmain(){cin>>n>>m;for(inti=1;i<=n;i++)for(intj=1;j<=m;j++)cin>>map[i][j];// 遍历地图，寻找连通块的入口for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){if(map[i][j]=='W'){// 如果是没被标记过的目标ans++;// 发现新岛屿/湖泊dfs(i,j);// 淹没整块区域}}}cout<<ans<<endl;return0;}

四、 核心避坑指南（踩坑复盘）

1. 方向数组写错：dx和dy一定要配对（比如dx=0时，dy是1和-1，代表左右移动）。八方向千万别漏了。
2. 忘记恢复现场：路径题（如全排列）递归后一定要把vis改回0，否则只能跑出一条路径。
3. 越界检查：nx >= 1 && nx <= n必须写在递归之前，不然访问到map[0][0]或随机内存，直接Segmentation Fault（RE）。
4. 起点终点特殊处理：如果题目起点本身就有障碍，记得提前return；如果终点是特殊字符，记得在起点处就标记。
5. 连通块的外圈保护：如果题目是经典的“01迷宫”或“填涂颜色”，为了防止 DFS 跑出地图边界导致 RE，经常在输入地图时，把地图的四周多围一圈0，这样在 DFS 里就不用疯狂写边界判断了。

五、 进阶：如何避免 TLE（超时）？

如果 DFS 运行超时，说明你的搜索树太大了。此时需要加上剪枝（Pruning）。

• 可行性剪枝：当前步数已经超过已知最优解，直接return。
• 最优性剪枝：估算剩余步数加上当前步数，如果还不如目前的最优解，直接return。
• 记忆化搜索：把算过的状态存进数组（如 DP 数组），下次走到直接取结果。