DFS(算法简介+例题讲解）

大家好，欢迎来到IT知识分享网。

DFS（深度优先搜索）算法
是一种在图或树等数据结构中搜索的常见算法。

思想：

它从一个起始节点开始，沿着一条路径尽可能深入地搜索，直到无法继续或达到目标，然后回溯并探索其他路径。（不撞南墙不回头）。

关键：

1. 初始状态设置
2. 递归逻辑：正确实现递归，和对每个节点的处理
3. 回溯机制
4. 状态标记：标记已访问的，避免重复，同时要注意，递归后的操作（有时不能 =1/=0，需要+1，-1.下面例题就是这样）
5. 边界条件：有时需要if判断，数组定义时从1~n
6. 数据结构：

模板：

void dfs(Node node) { if (某些条件满足) { // 处理当前节点 } for (每个与当前节点相连的节点) { dfs(连接的节点); } } 

求细胞数量

题目描述

一矩形阵列由数字 $0$ 到 $9$ 组成，数字 $1$ 到 $9$ 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。
输入格式

第一行两个整数代表矩阵大小 $n$ 和 $m$。

接下来 $n$ 行，每行一个长度为 $m$ 的只含字符 0 到 9 的字符串，代表这个 $n\times m$ 的矩阵。
输出格式

一行一个整数代表细胞个数。

代码

#include<bits/stdc++.h> using namespace std; int p[4][2]={ 
     { 
     0,1},{ 
     -1,0},{ 
     0,-1},{ 
     1,0}}; int m,n,sum=0; bool b[105][105]; char a[102][102]; void dfs(int x,int y) { 
      b[x][y]=1; for(int i=0;i<4;i++) if(x+p[i][0]>=0&&x+p[i][0]<n&&y+p[i][1]>=0&&y+p[i][1]<m&&a[x+p[i][0]][y+p[i][1]]!='0'&&b[x+p[i][0]][y+p[i][1]]==0) //范围一定别忘了限定  { 
      dfs(x+p[i][0],y+p[i][1]);//在范围内，未标记，又符合，就递归，直至不满足，退出 } } int main() { 
      cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>a[i][j]; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(a[i][j]!='0'&&b[i][j]==0)//别忘加引号，这是字符 { 
      sum++;dfs(i,j);//sum++,在函数里找并标记一个完整细胞 } cout<<sum; } 

这个是比较简单的，连通体类型，同类型P1596 水坑，可以练习

[USACO1.5] 八皇后 Checker Challenge

题目描述

一个如下的 $6\times 6$ 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列 $246135$ 来描述，第 $i$ 个数字表示在第 $i$ 行的相应位置有一个棋子，如下：

行号 $123456$

列号 $246135$

输入格式

一行一个正整数 $n$，表示棋盘是 $n\times n$ 大小的。

输出格式

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

代码

 #include<bits/stdc++.h> using namespace std; int a[100],b[100],c[100],d[100],n,s; //每行、每列有且只有一个，每条对角线上至多有一个棋子，开四个数组来标记  void print() { 
      s++;//加上一种结果  if(s<=3) { 
      for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<endl; } } int search(int i) { 
      for(int j=1;j<=n;j++) { 
      if(b[j]==0&&c[i+j]==0&&d[i-j+n]==0) { 
      a[i]=j,b[j]=1,c[i+j]=1,d[i-j+n]=1; //a来控制行，存储的位置也是最终结果，b控制列，c控制其中一条对角线（行列相加相等），d另一条对角线（行列相减相等+n,保证数据范围）  if(i==n) //标记到最后一行  print();//调用输出的函数  else search(i+1);//下一行找  b[j]=0,c[i+j]=0,d[i-j+n]=0;//没找到，返回时，取消标记  } } return 0; } int main() { 
      cin>>n; search(1); cout<<s<<endl; return 0; } 

这也是一个经典的例题，八皇后类型，关于对角线的约束条件，可以注意一下

[USACO06FEB] Backward Digit Sums G/S

题面翻译

有这么一个游戏：

写出一个 $1\sim n$ 的排列 $a$，然后每次将相邻两个数相加，构成新的序列，再对新序列进行这样的操作，显然每次构成的序列都比上一次的序列长度少 $1$，直到只剩下一个数字位置。

下面是一个例子：

• $3,1,2,4$；
• $4,3,6$；
• $7,9$；
• $16$。

最后得到 $16$ 这样一个数字。

现在想要倒着玩这样一个游戏，如果知道 $n$，以及最后得到的数字的大小 $sum$，请你求出最初序列 $a_i$（应该是一个 $1\sim n$ 的排列）。若答案有多种可能，则输出字典序最小的那一个。

我们称序列 $a=⟨a_1,a_2,\cdots ,a_n⟩$ 的字典序小于序列 $b=⟨b_1,b_2,\cdots ,b_n⟩$ 的字典序，当且仅当存在一个位置 $p$，满足 $a_1=b_1,a_2=b_2,\cdots ,a_{p-1}=b_{p-1},a_p<b_p$。
输入格式

共一行两个正整数 $n,sum$。
输出格式

输出包括一行，为字典序最小的那个答案。

当无解的时候，请什么也不输出。

代码

#include<bits/stdc++.h> using namespace std; int n,p; int a[13],c[13][13]; bool b[13]; void dfs(int dep ,int s) { 
      if(s>p) return ; if(dep>n)//选够n个数了  { 
      if(s==p)//结果=p  { 
      for(int i=1;i<=n;i++) cout<<a[i]<<" "; exit(0); //表示整个程序的结束  } return ; } for(int i=1;i<=n;i++)//i表示一行中数字，从1开始 。正好也符合，最小字典序  { 
      if(b[i]==false)//没选过i这个数字  { 
      b[i]=true;//答案数字不同，所以要标记一下 a[dep]=i;//把数字存入a数组  dfs(dep+1,s+i*c[n][dep]);//系数是递归三角，把答案从1循环开始试 b[i]=false; } } } int main() { 
      cin>>n>>p;//初始为n，也是进行n次。答案是n个数  //下面是关于杨辉三角排列  c[1][1]=1;//第一行  for(int i=2;i<=n;i++) //i表示行  for(int j=1;j<=i;j++)//一行一个数字，第n行，n个，j表示列  c[i][j]=c[i-1][j]+c[i-1][j-1]; dfs(1,0);//从第一个数开始，  return 0; } 

这个题目涉及到杨辉三角的规律，
由图可知，最后的结果是有关初始项多项式的答案，且系数和杨辉三角有关

奇怪的电梯

题目描述

呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 $i$ 层楼（$1\le i\le N$）上有一个数字 $K_i$（$0\le K_i\le N$）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： $3,3,1,2,5$ 代表了 $K_i$（$K_1=3$，$K_2=3$，……），从 $1$ 楼开始。在 $1$ 楼，按“上”可以到 $4$ 楼，按“下”是不起作用的，因为没有 $-2$ 楼。那么，从 $A$ 楼到 $B$ 楼至少要按几次按钮呢？

输入格式

共二行。

第一行为三个用空格隔开的正整数，表示 $N,A,B$（$1\le N\le 200$，$1\le A,B\le N$）。

第二行为 $N$ 个用空格隔开的非负整数，表示 $K_i$。

输出格式

一行，即最少按键次数，若无法到达，则输出 -1。

#include<bits/stdc++.h> using namespace std;//再开一个数组，用来更新比较，找到最小sum int a[201],A,B,N,m[201];//需要把sum放入函数调用中，不然它会连续改变 void dfs(int h,int sum)//如果用dfs,要不断更新，判断 { 
      m[h]=sum; if(h-a[h]<=N&&sum+1<m[h-a[h]] )//最高N  dfs(h-a[h],sum+1); if(a[h]+h>0&&sum+1<m[a[h]+h] ) //最低1  dfs(a[h]+h,sum+1); return; } int main() { 
      memset(m,0x3f,sizeof(m));//初始化为最大  cin>>N>>A>>B; for(int i=1;i<=N;i++) cin>>a[i]; dfs(A ,0);//当找不到时,m[B]对应的值极大 if(m[B]==0x3f3f3f3f) cout<<-1; else cout<<m[B]; } 

取数游戏

题目描述

一个 $N\times M$ 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻 $8$ 个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。

输入格式

第一行有一个正整数 $T$，表示了有 $T$ 组数据。

对于每一组数据，第一行有两个正整数 $N$ 和 $M$，表示了数字矩阵为 $N$ 行 $M$ 列。

接下来 $N$ 行，每行 $M$ 个非负整数，描述了这个数字矩阵。

输出格式

共 $T$ 行，每行一个非负整数，输出所求得的答案。

代码

#include<bits/stdc++.h> using namespace std; int p[8][2]={ 
     { 
     0,1},{ 
     1,0},{ 
     -1,0},{ 
     0,-1},{ 
     1,1},{ 
     -1,1},{ 
     1,-1},{ 
     -1,-1}}; int a[8][8],n,m,ma; int b[8][8]; void dfs(int x,int y,int z) { 
      if(y>m)//这个题用换行，y+1，x+1实现 { 
      dfs(x+1,0,z); return ; } if(x>n) { 
      ma=max(ma,z); return ; } dfs(x,y+1,z); if(b[x][y]==0) { 
      for(int i=0;i<8;i++) ++b[x+p[i][0]][y+p[i][1]];//这里是++，不能是=1，这样可能在某个递归中 dfs(x,y+1,z+a[x][y]);//又被改成零了，因为可能有多重标记，递归中直接改成零了 for(int i=0;i<8;i++) --b[x+p[i][0]][y+p[i][1]]; } } int main() { 
      int t; cin>>t; while(t--) { 
      memset(b,0,sizeof(b)); cin>>n>>m; ma=0; for(int i=1;i<=n;i++)//这里要从1开始到n,搜索边界很重要，在 for(int j=1;j<=m;j++)//这个题里正好不用判断因为一直y+1. cin>>a[i][j]; dfs(1,1,0); cout<<ma<<endl; } return 0; } 

高手去散步

题目描述

鳌头山上有 $n$ 个观景点，观景点两两之间有游步道共 $m$ 条。高手的那个它，不喜欢太刺激的过程，因此那些没有路的观景点高手是不会选择去的。另外，她也不喜欢去同一个观景点一次以上。而高手想让他们在一起的路程最长（观景时它不会理高手），已知高手的穿梭机可以让他们在任意一个观景点出发，也在任意一个观景点结束。
输入格式

第一行，两个用空格隔开的整数 $n$ 、 $m.$ 之后 $m$ 行，为每条游步道的信息：两端观景点编号、长度。

输出格式

一个整数，表示他们最长相伴的路程。

代码

#include<bits/stdc++.h> using namespace std; int n,m,a[55][55],mark[55],ans,ma;//这里用邻接矩阵去存放路线长度  void dfs(int x,int sum) { 
      ma=max(sum,ma);//从i开始的最大长度  for(int i=1;i<=n;i++) if(!mark[i]&&a[i][x]!=0) { 
      mark[i]=1; dfs(i,sum+a[i][x]); mark[i]=0; } } int main() { 
      int b,c,d; cin>>n>>m; while(m--) { 
      cin>>b>>c>>d; a[b][c]=d,a[c][b]=d;//此题b-c,c-b是双向  } for(int i=1;i<=n;i++) { 
      mark[i]=1; dfs(i,0); ans=max(ans,ma);//ma是从某点开始的最大长度  memset(mark,0,sizeof(mark)); } cout<<ans; } 

还有一道P1700 [USACO19OPEN] Milk Factory B可以看一下