深度优先搜索（dfs）练习题及详细解答
相信很多⼈在最先开始学习深度优先搜索（dfs）的时候，都是⼀脸懵逼，但其实只要通过⼀定数⽬的练习，你就可以熟练运⽤这⼀算法（骗分神器）了，下⾯是我挑选出的⼏道dfs题⽬（源⾃洛⾕），相信你练习完了以后，对这⼀神奇算法也会有更深的体会。
⾸先是⼀道dfs的⼊门题：
下⾯是代码
#include<bits/stdc++.h>//万能头
using namespace std;
char keyword[]="yizhong";
char square[101][101];//输⼊数组
char book[101][101];//记录变化的数组
int drive[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};//⼋⽅向数组
int n;//n*n
struct road{//记录路径的结构体
int x , y;
};
road way[7];//记录路径
void dfs(int x ,int y ,int state ,int dir)//dir是⽅向，搜索的⽅向，x，y是开始搜索的坐标，state当前搜索到了第⼏个字母
{
if(state>6){
for(int i =0; i <7; i++)//如果搜索完了，说明所求的就是想要的
book[way[i].x][way[i].y]=1;//记录路径
}
else if(state <=6){
int dx = x + drive[dir][0];
int dy = y + drive[dir][1];
if(state ==6|| square[dx][dy]== keyword[state+1]){//如果state等于6，说明已经搜索完了
way[state].x = x;//记录路径
way[state].y = y;namespace是干嘛的
dfs(dx,dy,state+1,dir);//搜索下个节点，如果修改了state的值下⾯，如state++，下⾯就要加⼀⾏state--，以达到回溯的⽬的，这⾥偷懒了，就直接state+1了}
}
}
int main()
{
cin>>n;
for(int i =0; i < n ; i++)
for(int j =0; j < n ; j++){
cin>>square[i][j];
}
for(int i =0; i < n ; i++)
for(int j =0; j < n ; j++){
if(square[i][j]=='y'){
for(int k =0; k <8; k++){
if(square[i+drive[k][0]][j+drive[k][1]]=='i'){//如果满⾜条件，开始深搜
dfs(i,j,0,k);
}
}
}
}
for(int i =0; i < n ; i++){
for(int j =0; j < n ; j++){
if(book[i][j])cout<<square[i][j];//输出
else cout<<'*';
}
cout<<endl;
}
return0;
}//总的来说这还是⼀道不错的⼊门题
第⼆题：
这道题与上道题有些许不同，这⾥需要⽤到⼀个⼩的优化，也就是我们常说的剪枝下⾯是代码：
#include<bits/stdc++.h>
using namespace std;
int N , Sum;
bool flag =false;//记录是否搜索完毕的标志
int ans[20], bd[20], book[20];//分别是储存答案的数组，模板数组，判重数组
int getC(int a ,int b)//获取组合数的函数
{
int sum =1;
if( b > a/2) b = a - b;
for(int i =1; i <= b ; i++)
sum = sum * a--/ i;
return sum;
}
void st(int n)//初始化的函数，利⽤杨辉三⾓形各项系数为相应n-1的组合数，初始化⼀个模板数组
{
int sum =0;
for(int i =0; i < n ; i++)
bd[i]=getC(n-1,i);
}
void dfs(int sum ,int step)//深搜
{
if(sum > Sum)return;//剪枝，即如果这⾥的sum⽐所需要的Sum还要⼤的话就没有必要搜索下去了if(step == N){//如果满⾜条件，标记，返回
if(sum == Sum) flag =true;
return;
}
for(int i =1; i <= N ; i++)
{
if(!book[i]){//如果没有搜索过
ans[step]= i;
book[i]=1;
dfs(sum + ans[step]* bd[step], step +1);
if(flag)return;//这⾥很重要，如果没有，搜索会继续进⾏下去
book[i]=0;
}
}
}
int main()
{
cin>>N>>Sum;
st(N);// for(int i = 0 ; i < N ; i++) cout<<bd[i]<<" ";cout<<Sum；这⾥是检查bd的内容
dfs(0,0);
if(flag){
for(int i =0; i < N ; i++)
cout<<ans[i]<<" ";//输出答案，结束
}
return0;
}
这⾥简单介绍了剪枝，如果不利⽤这个剪枝，可能会TLE（我没有试过）
第三题：
题⽬链接：下⾯是代码：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。