深度优先算法（2）——例题详解

2.2 DFS例题详解

本章将对于DFS的例题进行讲解，讲清楚DFS的用途。代码仓库链接

2.2.0 题目清单

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 k=2k=2时的代码：

_for(i,n){_for(j,n){if(i==j)continue;cout<<i<<' '<<j<<endl;}}

当k = 3 k=3k=3时与这段代码类似，但是有3 33层循环，k = 4 , 5 k=4,5k=4,5的时候显然也一样。既然这样为了缩短代码（虽然感人的数据范围告诉我们k ≤ 4 k\le 4k≤4），我们得找到一种控制循环层数的办法。

这种方法就是递归，具体方法就是将循环体变成函数调用，循环层数变成递归层数。相信编程功底扎实的读者知道我在说什么。

voidfun(args){if(结束条件)return;for(...){fun();}}

通过这样就可以实现任意层数的递归。

从定义上这道题也属于DFS（递归+回溯），不过不是最经典的用法，但也用到了递归思想。

代码位置：2\problems\B3621.cpp

#include<bits/stdc++.h>usingnamespacestd;intn,k;inta[6];// n最大5，开6足够voiddfs(intdepth){// 递归终点：已经填完n个位置，直接输出if(depth==n){for(inti=0;i<n;i++){cout<<a[i]<<" ";}cout<<endl;return;}// 当前位置枚举 1~k 所有数，可重复选，不用visfor(intnum=1;num<=k;num++){a[depth]=num;dfs(depth+1);// 填下一位}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n>>k;dfs(0);return0;}

2.2.2 B3622 枚举子集

题意简述

有n nn名同学，可以选择任意名同学参加合唱，输出所有可能性（Y=YES,N=NO）

算法实现

这道题有两种思路：状压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

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti=0;i<n;i++)#define_rep(i,a,b)for(inti=a;i<b;i++)#defineendl'\n'intn;boola[10];voiddfs(intdepth){if(depth==n){_for(i,n)cout<<(a[i]?'Y':'N');cout<<endl;return;}a[depth]=0;dfs(depth+1);a[depth]=1;dfs(depth+1);}intmain(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;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

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti=0;i<n;i++)#define_rep(i,a,b)for(inti=a;i<b;i++)#defineendl'\n'boolvis[10];// 数据范围比较小也不用考虑用vector<bool>状态压缩inta[10];intn;// dfs函数要用就设为全局voiddfs(intdepth){_for(i,n){if(!vis[i]){if(depth==n){// 递归到底，输出a[depth-1]=i+1;_for(i,n)cout<<setw(5)<<a[i];cout<<endl;return;}vis[i]=true;a[depth-1]=i+1;dfs(depth+1);vis[i]=false;}}}intmain(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;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

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti=0;i<n;i++)#define_rep(i,a,b)for(inti=a;i<b;i++)#defineendl'\n'intsx,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(x==fx&&y==fy)return1;// 到终点了intcnt=0;_for(i,4){// 越界检查if((x+dx[i]<0)||(y+dy[i]<0))continue;if((x+dx[i]>=n)||(y+dy[i]>=m))continue;if(!matrix[x+dx[i]][y+dy[i]]&&(!vis[x+dx[i]][y+dy[i]])){vis[x+dx[i]][y+dy[i]]=true;// 添加标记cnt+=dfs(x+dx[i],y+dy[i]);vis[x+dx[i]][y+dy[i]]=false;// 撤销标记}}returncnt;// 既然没有到达终点的可能（已经排除了）那么遇到死胡同直接返回0即可无需判断}intmain(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m>>t;cin>>sx>>sy>>fx>>fy;sx--;sy--;fx--;fy--;vis[sx][sy]=true;// 先给起点打上标记while(t--){intx,y;cin>>x>>y;x--;y--;matrix[x][y]=true;}cout<<dfs(sx,sy)<<endl;}

剩下的题目建议自主完成，以熟练掌握DFS算法的应用