2.2 DFS例题详解本章将对于DFS的例题进行讲解讲清楚DFS的用途。代码仓库链接2.2.0 题目清单序号题号题目名称题型分类难度定位核心考点1B3621枚举元组回溯-基础框架入门多层递归、字典序枚举2B3622枚举子集回溯-指数枚举入门选/不选模型、指数型枚举3P1706全排列问题回溯-排列枚举普及-排列型枚举、vis 标记、回溯恢复现场4P1605迷宫回溯-约束枚举普及-标记回溯、递归深入5P1036选数回溯-组合枚举普及-组合枚举、素数判断、可行性剪枝6P1088火星人回溯-排列生成普及-字典序搜索、排列生成、剪枝7P1149火柴棒等式回溯-剪枝普及-指数型枚举、可行性剪枝8P1025数的划分回溯-组合方案提高-整数拆分、去重回溯9B3625迷宫寻路网格 DFS普及-方向数组、访问标记、网格 DFS 模板10P1605迷宫网格 DFS-路径计数普及-障碍规避、路径回溯11P1644跳马问题网格 DFS-剪枝普及-棋盘 DFS、状态空间剪枝12P1219八皇后回溯-强约束普及/提高-行列对角线约束、经典剪枝13P1451求细胞数量FloodFill-连通块普及-4 连通块统计、染色14P1596Lake Counting SFloodFill-连通块普及-8 连通块、水塘计数15P1331海战FloodFill-图形校验普及-矩形连通块校验、合法图形判断16P1506拯救 oibh 总部FloodFill-封闭区域普及-边界连通块剔除、内部封闭区域17P1019单词接龙回溯-字符串搜索提高-字符串重叠处理、DFS 剪枝18P5194Scales回溯-最优性剪枝提高-子集和枚举、最优性剪枝19P3956棋盘回溯-综合普及/提高状态设计、DFS 综合20P1074靶形数独回溯-搜索集大成提高多维度冲突检测、剪枝优化2.2.1 B3621 枚举元组题意简述给定n , k n,kn,k输出所有满足组内元素∈ [ 1 , k ] \in [1,k]∈[1,k]的n nn元组其中n nn元组意为有n nn个不同元素的数列注意不是集合数列有顺序算法分析首先让我们观察样例样例是一个2元组第一个元素依次从1 11到k kk固定第一个元素的情况下第二个元素也依次从1 11到k kk但是不与第一个元素重合由此可以写出当k 2 k2k2时的代码_for(i,n){_for(j,n){if(ij)continue;couti jendl;}}当k 3 k3k3时与这段代码类似但是有3 33层循环k 4 , 5 k4,5k4,5的时候显然也一样。既然这样为了缩短代码虽然感人的数据范围告诉我们k ≤ 4 k\le 4k≤4我们得找到一种控制循环层数的办法。这种方法就是递归具体方法就是将循环体变成函数调用循环层数变成递归层数。相信编程功底扎实的读者知道我在说什么。voidfun(args){if(结束条件)return;for(...){fun();}}通过这样就可以实现任意层数的递归。从定义上这道题也属于DFS递归回溯不过不是最经典的用法但也用到了递归思想。代码位置2\problems\B3621.cpp#includebits/stdc.husingnamespacestd;intn,k;inta[6];// n最大5开6足够voiddfs(intdepth){// 递归终点已经填完n个位置直接输出if(depthn){for(inti0;in;i){couta[i] ;}coutendl;return;}// 当前位置枚举 1~k 所有数可重复选不用visfor(intnum1;numk;num){a[depth]num;dfs(depth1);// 填下一位}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cinnk;dfs(0);return0;}2.2.2 B3622 枚举子集题意简述有n nn名同学可以选择任意名同学参加合唱输出所有可能性YYES,NNO算法实现这道题有两种思路状压DP、DFS这里简单介绍一下状压DP用一个n nn位二进制数表示集合s ss的子集其中第i ii位如果为1 11则表示取该位为0 00则表示不取。这种算法会在之后讲到代码位于2\problems\P3622_1.cpp下面是正解DFS也是这道题算法标签的算法首先按照全部N到底当N的数量等于n nn的时候就回溯把最底下的N变成Y再来一次代码非常简单。代码位置2\problems\B3622_2.cpp#includebits/stdc.husingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti0;in;i)#define_rep(i,a,b)for(intia;ib;i)#defineendl\nintn;boola[10];voiddfs(intdepth){if(depthn){_for(i,n)cout(a[i]?Y:N);coutendl;return;}a[depth]0;dfs(depth1);a[depth]1;dfs(depth1);}intmain(){ios::sync_with_stdio(0);cin.tie(0);cinn;dfs(0);}前两道例题是DFS最基础的用法只有递归回溯但是这显然不是DFS最常用的用法太简单了实际上深度优先搜索的算法最典型的用法是下面的几道例题。2.2.3 P1706 全排列问题题意简述给出一个值n nn要求输出1 − n 1-n1−n的所有全排列按照字典序顺序算法分析这道题有两种思路使用STL和使用DFS。其中使用STL就没什么必要学习了详见2\problems\P1706_1.cpp使用DFS思考一下我们生成全排列的过程以5个数字全排列为例先从1 11开始还有剩余数字那就往后添加2 22一直到最后得到序列1 , 2 , 3 , 4 , 5 1,2,3,4,51,2,3,4,5。到了5 55之后没有其他数字了就进行回溯得出倒数第二个数字还能用5 55得到序列1 , 2 , 3 , 5 , 4 1,2,3,5,41,2,3,5,4。倒数第二个数字也没有其他情况了继续回溯得到序列1 , 2 , 4 , 3 , 5 1,2,4,3,51,2,4,3,5以此类推得到全部全排列发现符合DFS一条路走到黑的特点每一个位置都能使用前面位置未使用过的数字哪些数字用过使用vis数组记录visa的缩写DFS的算法还是重在熟练。代码位置2\problems\P1706_2.cpp#includebits/stdc.husingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti0;in;i)#define_rep(i,a,b)for(intia;ib;i)#defineendl\nboolvis[10];// 数据范围比较小也不用考虑用vectorbool状态压缩inta[10];intn;// dfs函数要用就设为全局voiddfs(intdepth){_for(i,n){if(!vis[i]){if(depthn){// 递归到底输出a[depth-1]i1;_for(i,n)coutsetw(5)a[i];coutendl;return;}vis[i]true;a[depth-1]i1;dfs(depth1);vis[i]false;}}}intmain(){ios::sync_with_stdio(0);cin.tie(0);cinn;dfs(1);return0;}2.2.4 P1605 迷宫题意简述给出一个迷宫其中有n nn个障碍物给出这些障碍物的坐标( x , y ) (x,y)(x,y)并给出起点坐标( s x , s y ) (sx,sy)(sx,sy)和终点坐标( f x , f y ) (fx,fy)(fx,fy)问从起点走到终点并不经过障碍物有多少种方法算法分析这道题是一道迷宫的问题可以使用DFS算法解决我们先想一想用人脑如何比较公式化地用DFS思维解这道题从起点出发只要能向下走就向下走当然也可以选择其他方向如果不能向下走就考虑向左向右向上走当走到终点了就增加答案数量当走进死胡同就回到上一个岔路口重新选择这是一道经典的DFS模板题要熟记代码灵活转化代码位置2\problems\P1605.cpp#includebits/stdc.husingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti0;in;i)#define_rep(i,a,b)for(intia;ib;i)#defineendl\nintsx,sy,fx,fy;intn,m,t;boolmatrix[5][5];boolvis[5][5];intdx[]{1,0,-1,0};// 方向数组intdy[]{0,1,0,-1};intdfs(intx,inty){if(xfxyfy)return1;// 到终点了intcnt0;_for(i,4){// 越界检查if((xdx[i]0)||(ydy[i]0))continue;if((xdx[i]n)||(ydy[i]m))continue;if(!matrix[xdx[i]][ydy[i]](!vis[xdx[i]][ydy[i]])){vis[xdx[i]][ydy[i]]true;// 添加标记cntdfs(xdx[i],ydy[i]);vis[xdx[i]][ydy[i]]false;// 撤销标记}}returncnt;// 既然没有到达终点的可能已经排除了那么遇到死胡同直接返回0即可无需判断}intmain(){ios::sync_with_stdio(0);cin.tie(0);cinnmt;cinsxsyfxfy;sx--;sy--;fx--;fy--;vis[sx][sy]true;// 先给起点打上标记while(t--){intx,y;cinxy;x--;y--;matrix[x][y]true;}coutdfs(sx,sy)endl;}剩下的题目建议自主完成以熟练掌握DFS算法的应用