DFS深度优先搜索做题步骤与万能模板DFS 是蓝桥杯和算法竞赛中的绝对核心。很多初学者容易晕头转向其实只要在写代码前问自己一个问题这道题是“找所有路径排列/迷宫”还是“找连通块涂色/数岛屿”注 除了上述两类DFS 还常用于树/图的遍历无需回溯以及子集/组合问题需要回溯。但万变不离其宗核心都是基于“是否撤销现场”来划分的。一、 第一步30 秒判断题型题型核心特征是否需要回溯代表题目路径型 / 选择型每个元素/格子不能重复走求所有可能的方案需要(vis恢复为 0)P1605 迷宫、P1706 全排列、P1219 八皇后连通块型每个格子只属于一个区域求有几块不需要(永久标记)P1596 湖计数、P1162 填涂颜色二、 路径型 / 选择型 DFS 模板特征必须“恢复现场”回溯因为要尝试所有分支。#includeiostreamusingnamespacestd;intn,m;intans0;intvis[105];// 一维标记数字是否用过二维地图则用 vis[105][105]voiddfs(intstep){// 1. 终止条件到达目的地或者选完了所有数if(stepn){// 或者 (x endX y endY)ans;return;}// 2. 扩展遍历所有可能的选择for(inti1;in;i){// 3. 合法性判断if(!vis[i]){// 4. 标记当前状态vis[i]1;// 5. 递归下一层dfs(step1);// 6. 回溯恢复现场核心vis[i]0;}}}intmain(){cinn;dfs(1);// 从第一步开始coutansendl;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(xexyey){ans;// 到达终点方案数1return;}for(inti0;i4;i){intnxxdx[i],nyydy[i];// 不越界 且 不是障碍 且 没走过if(nx1nxnny1nymmap[nx][ny]0!vis[nx][ny]){vis[nx][ny]1;// 标记dfs_maze(nx,ny);// 递归vis[nx][ny]0;// 回溯}}}三、 连通块型 DFS 模板特征一旦走到某个格子就把它彻底同化绝不回头。#includeiostreamusingnamespacestd;intn,m,ans0;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(inti0;i4;i){intnxxdx[i];intnyydy[i];// 3. 合法性判断不越界、且是目标地形如 Wif(nx1nxnny1nymmap[nx][ny]W){// 4. 递归不需要回溯dfs(nx,ny);}}}intmain(){cinnm;for(inti1;in;i)for(intj1;jm;j)cinmap[i][j];// 遍历地图寻找连通块的入口for(inti1;in;i){for(intj1;jm;j){if(map[i][j]W){// 如果是没被标记过的目标ans;// 发现新岛屿/湖泊dfs(i,j);// 淹没整块区域}}}coutansendl;return0;}四、 核心避坑指南踩坑复盘方向数组写错dx和dy一定要配对比如dx0时dy是1和-1代表左右移动。八方向千万别漏了。忘记恢复现场路径题如全排列递归后一定要把vis改回0否则只能跑出一条路径。越界检查nx 1 nx n必须写在递归之前不然访问到map[0][0]或随机内存直接Segmentation FaultRE。起点终点特殊处理如果题目起点本身就有障碍记得提前return如果终点是特殊字符记得在起点处就标记。连通块的外圈保护如果题目是经典的“01迷宫”或“填涂颜色”为了防止 DFS 跑出地图边界导致 RE经常在输入地图时把地图的四周多围一圈0这样在 DFS 里就不用疯狂写边界判断了。五、 进阶如何避免 TLE超时如果 DFS 运行超时说明你的搜索树太大了。此时需要加上剪枝Pruning。可行性剪枝当前步数已经超过已知最优解直接return。最优性剪枝估算剩余步数加上当前步数如果还不如目前的最优解直接return。记忆化搜索把算过的状态存进数组如 DP 数组下次走到直接取结果。