DFS最重要的是理清搜索顺序！
ps：这是我入门dfs时写的博客，后来dfs渐渐熟练了，也补充了一些题目上去（带原题和代码）。个人感觉整篇博文从上到下确实由易到难，代码也由开始的冗长变得渐渐精简。
自学DFS看的视频：
小甲鱼：讲原理
青岛大学-王卓：讲的较为全面的基本知识p122-124
自学之后的题目总结：【DFS】题目总结
推荐AcWing y总的讲解！
深度优先搜索(DFS, Depth First Search)是一个针对图和树的遍历算法。早在19世纪就被用于解决迷宫问题。
它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。（参考“可参考资料2”）
对图的理解可见：
图的详解
大概步骤：
深度优先搜索用一个数组存放产生的所有状态。
（1） 把初始状态放入数组中，设为当前状态；
（2） 扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当前状态；
（3） 判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一状态；
（4） 判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法。
（5） 如果数组为空，说明无解。
对于pascal语言来讲，它支持递归，在递归时可以自动实现回溯（利用局部变量）所以使用递归编写深度优先搜索程序相对简单，当然也有非递归实现的算法。（摘自百度百科）
题目描述
输入
第一行输入一个整数N，表示共有N组测试数据
每一组数据都是先输入该地图的行数m(0<m<100)与列数n(0<n<100)，
然后，输入接下来的m行每行输入n个数，表示此处有水还是没水（1表示此处是水池，0表示此处是地面）
输出
输出该地图中水池的个数。
每个水池的旁边（上下左右四个位置）如果还是水池的话的话，它们可以看做是同一个水池。
样例输入
2
3 4
1 0 0 0
0 0 1 1
1 1 1 0
5 5
1 1 1 1 0
0 0 1 0 1
0 0 0 0 0
1 1 1 0 0
0 0 1 1 1
样例输出
2
3
一个总结：
这是一道基础dfs题，适合我这样的初学者；
大致思路是：
定义一个void dfs()函数，功能是如果二维数组某点为1，则判断其上下左右是否为为1，若为1，使之为0，并递归调用dfs对其周围进行搜索判断；
其中，若传入一个已知为1的点，对它周围搜索，肯定会搜索会本点并使之为0，则无需单独对该点单独操作；
且，if中的数组的参数与调用时传入的参数相同，如此方便记忆。
void函数如：
void dfs(int a,int b) //深度优先搜索函数，一旦调用，一个点周围连续的地方都记为0；
{
if(arr[a-1][b]==1){arr[a-1][b]==0;dfs(a-1,b); //上
}
if(arr[a+1][b]==1){arr[a+1][b]==0;dfs(a+1,b); //下
}
if(arr[a][b-1]==1){arr[a][b-1]==0;dfs(a,b-1); //左
}
if(arr[a][b+1]==1){arr[a][b-1]==0;dfs(a,b+1); //右
}
}
主函数：
int main(void)要传入void（目前不知道原因，记就是了）
此题的常规操作：
输入多组数据用while(t--)
逐个传入二维数组常规操作：
for(int i=1;i<=n;i++) //逐个输入二维数组的常规操作
{
for(int j=0;j<=m;j++)
{
cin>>arr[i][j];
}
}
遍历二维数组也要两层循环，其中从1开始，因为我们计数从1开始，简化操作；
i、j均小于等于；
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{......}
}
其他操作：
1、万能头；
2、可以宏定义一个N表示水池的边界，其中105是从1到100再上下左右+1 为105（自行体会）；
#include<bits/stdc++.h> //万能头
#define N 105
还可以再看看链接里的讲解；
整体代码：
#include<bits/stdc++.h> //万能头
#define N 105
using namespace std;
int arr[N][N];
void dfs(int a,int b) //深度优先搜索函数，一旦调用，一个点周围连续的地方都记为0；
{
if(arr[a-1][b]==1){arr[a-1][b]==0;dfs(a-1,b); //上
}
if(arr[a+1][b]==1){arr[a+1][b]==0;dfs(a+1,b); //下
}
if(arr[a][b-1]==1){arr[a][b-1]==0;dfs(a,b-1); //左
}
if(arr[a][b+1]==1){arr[a][b-1]==0;dfs(a,b+1); //右
}
}
int main(void) //int main(void) 常规套路要记下来
{
int t;
int n,m;
cin>>t;
while(t--)
{
int cnt=0;
cin>>n>>m;
for(int i=1;i<=n;i++) //逐个输入二维数组的常规操作
{
for(int j=0;j<=m;j++)
{
cin>>arr[i][j];
}
}
for(int i=1;i<=n;i++) //对二维数组进行遍历
{
for(int j=1;j<=m;j++)
{
if(arr[i][j]==1)
{
cnt++; //核心步骤
dfs(i,j);
}
}
}
cout<<cnt<<endl;
}
return 0;
}
模型一：
六角星问题
题目：
如图【1.png】所示六角形中，填入1~12的数字。使得每条直线上的数字之和都相同。
图中，已经替你填好了3个数字，请你计算星号位置所代表的数字是多少？
本题小总结：
1、讲图中每一个节点抽象成一个数字，一共13个节点，用数组来存放其放的数字；
2、用v数组（visited）来表示一个数字是否被用过，如：
v[1]=1,即数字1已经被用过；
v[4]=0,即数字4未被用过。
如：
#include<bits/stdc++.h>
using namespace std;
int a[13]={0},v[13]={0}; //a是表示图的数组，v是表示某个数字是否使用过visited
void dfs(int x);
void jude(void); //声明一下；
int main(void)
{
int i;
a[1]=1;
a[2]=8;
a[12]=3; //给图标号
v[1]=1;
v[8]=1;
v[3]=1; //给使用过的数字mark一下；
dfs(1);
return 0;
}
3、若x是1，2，12这三个已经有了的，直接进行下一步dfs；
如果x是13，则进行判断；
前面有这两个if判断后，走到这一步的都是非1，2，12，13的，接下来是核心操作：
若数字未被用过，就直接把该数字放进去，然后一直向下递归（dfs(x+1)），到13后判断，如果不符合题意，就退回到dfs(x+1)的下一步，v[i]=0,即之前用过的那个数字行不通，不用那个数字，从那个数字之后往下尝试递归。
如下：
void dfs(int x)
{
int i,b[6]; //b代表六条边
if(x==1||x==2||x==12) //如果x是1，2，12这三个一开始已经有的，就直接递归到下一个；
{
dfs(x+1);
return ;
}
if(x==13) //如果x是13，最后一个，就进行判断；
{
jude();
}
for(i=1;i<13;i++) //核心操作：从数字1到12，如果有没有用过（v[数字]=0），就让它被用，放入下一个空格，然后反复调用
{
if(v[i]==0)
{
v[i]=1;
a[x]=i;
dfs(x+1);
v[i]=0;
}
}
}
4、这一步是定义判断函数，判断每条表之和是否相等。相当通俗易懂，直接放代码：
void jude(void)
{
int i,b[6];
b[0]=a[1]+a[3]+a[6]+a[8];
b[1]=a[1]+a[4]+a[7]+a[11];
b[2]=a[2]+a[3]+a[4]+a[5];
b[3]=a[2]+a[6]+a[9]+a[12];
b[4]=a[5]+a[7]+a[10]+a[12];
b[5]=a[8]+a[9]+a[10]+a[11];
for(i=1;i<6;i++)
{
if(b[i]!=b[i-1])
{
return;
}
}
cout<<a[6];
}
总体思想就是递归和回溯，加上数组的运用。
整体代码：
#include<bits/stdc++.h>
using namespace std;
int a[13]={0},v[13]={0}; //a是表示图的数组，v是表示某个数字是否使用过visited
void dfs(int x);
void jude(void); //声明一下；
int main(void)
{
int i;
a[1]=1;
a[2]=8;
a[12]=3; //给图标号
v[1]=1;
v[8]=1;
v[3]=1; //给使用过的数字mark一下；
dfs(1);
return 0;
}
void dfs(int x)
{
int i,b[6]; //b代表六条边
if(x==1||x==2||x==12) //如果x是1，2，12这三个一开始已经有的，就直接递归到下一个；
{
dfs(x+1);
return ;
}
if(x==13) //如果x是13，最后一个，就进行判断；
{
jude();
}
for(i=1;i<13;i++) //核心操作：从数字1到12，如果有没有用过（v[数字]=0），就让它被用，放入下一个空格，然后反复调用
{
if(v[i]==0)
{
v[i]=1;
a[x]=i;
dfs(x+1);
v[i]=0;
}
}
}
void jude(void)
{
int i,b[6];
b[0]=a[1]+a[3]+a[6]+a[8];
b[1]=a[1]+a[4]+a[7]+a[11];
b[2]=a[2]+a[3]+a[4]+a[5];
b[3]=a[2]+a[6]+a[9]+a[12];
b[4]=a[5]+a[7]+a[10]+a[12];
b[5]=a[8]+a[9]+a[10]+a[11];
for(i=1;i<6;i++)
{
if(b[i]!=b[i-1])
{
return;
}
}
cout<<a[6];
}
在N*N格的国际象棋上摆放N个皇后，使其不能互相攻击，
即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
如果出现x+y==某个常数，那么它们就在一条对角线上了。
+n是因为数组下标不能为负，加的一个参数而已。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10;
int n;
char g[N][N];
int lie[N],zdj[N],fdj[N];
void dfs(int u)//u是行 每行只能有一个
{
if(u==n)//结束
{
for(int i=0;i<n;i++) cout<<g[i]<<endl;
cout<<endl;
return;
}
for(int i=0;i<n;i++)
{
if(!lie[i]&&!zdj[u+i]&&!fdj[n-u+i])
{
g[u][i]='Q';
lie[i]=1;
zdj[u+i]=1;fdj[n-u+i]=1;
dfs(u+1);//下一行
g[u][i]='.';//恢复现场
lie[i]=0;
zdj[u+i]=0;fdj[n-u+i]=0;
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
g[i][j]='.';
}
}
dfs(0);
return 0;
}
解法在这里：
一个模板。
100 可以表示为带分数的形式：100 = 3 + 69258 / 714 ， 还可以表示为：100 = 82 + 3546 / 197
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
题目要求：
从标准输入读入一个正整数N (N<1000*1000)
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
小总结：
1、主函数：输入、调用dfs函数，输出；
2、dfs函数，不断递归和某个数字是否使用等操作；
3、jude判断函数，调用sum函数组合出许多种数字组合并判断是否能符合题意；
4、sum函数，将传入的数字一个个组成如题所示的数字，如24567这种；
dfs函数里的注释：
若某个数字没有用过，则将它使用，并进入下一层递归，然后自然地就到了jude，若可以则count1++；
行或不行都回溯回来，重新用不同的数字，即v[i]=0,然后循环到下一个数字；
本题有两个坑点：
1、分母不能做除数，要进行判断；
2、可能报“reference to ’ *** ’ is ambiguous”的错，因为用的是万能头，我定义的变量名跟里面的属性或者方法重名了，将***里的变量名改一下即可。
整体代码：
#include<bits/stdc++.h>
using namespace std;
long long count1=0,p;
int a[10],v[10]={0};
void dfs(int n); //一堆声明；
void jude(void);
int sum(int x,int y);
int main(void)
{
cin>>p;
dfs(1);
cout<<count1;
return 0;
}
void dfs(int n)
{
int i;
if(n>9) //当递归到9以上即数字都用完了，可以进行判断
{
jude();
}
for(i=1;i<10;i++) //反复递归
{
if(!v[i])
{
v[i]=1; //若某个数字没有用过，则将它使用，并进入下一层递归，然后自然地就到了jude，若可以则count1++；
a[n]=i; //行或不行都回溯回来，重新用不同的数字，即v[i]=0,然后循环到下一个数字；
dfs(n+1);
v[i]=0;
}
}
}
void jude(void)
{
int x,y,z;
for(int i=0;i<8;i++)
{
for(int j=i+1;j<9;j++) //这个循环是步骤最多的地方；把每一种可能的数字组合都试了一遍；
{ //且，数字可以不连续，因为某个数字若已经用过就跳过去了；
x=sum(1,i);
y=sum(i+1,j);
z=sum(j+1,9);
if((p-x)*z==y) //即题目中的分式等式
{
count1++;
}
}
}
}
int sum(int x,int y)
{
int s=0;
if(y==0) //分母不能做除数
{
return 0;
}
for(x;x<y;x++)
{
s=s*10+a[x];
}
return s;
}
摘自参见资料5
2-4题都有相同的一段代码：
这个函数做的就是把每一种情况列举一次，再用jude函数筛选。
这种模型适合的题目是：给你一个图让你填不重复的数。
void dfs(int n)
{
int i;
if(n>x)
jude();
for(i=1;i<=x;i++)
if(v[i])
{
v[i] = 0;
a[n] = i;
dfs(n+1);
v[i] = 1;
}
}
#include<iostream>
using namespace std;
typedef long long ll;
//======================
const int N=100+10;
char a[N][N];
int vis[N][N];
int ans=0;
int dx[8]={-1,0,1,-1,1,-1,0,1};
int dy[8]={-1,-1,-1,0,0,1,1,1};
int n,m;
void dfs(int x,int y)//坐标
{
if(vis[x][y]) return;
vis[x][y]=1;
for(int i=0;i<8;i++)
{
int xx=x+dx[i];
int yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&a[xx][yy]=='W')
{
dfs(xx,yy);
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%s",a[i]+1);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(!vis[i][j]&&a[i][j]=='W')
{
ans++;
// cout<<i<<" "<<j<<endl;
dfs(i,j);
}
}
cout<<ans;
return 0;
}
1、图的详解
2、较为全面的大佬博客
3、算法源码，用C++、C和Java
4、简单的水池问题
5、大佬的模型例题，好几道
6、非常厉害的入门模板
7、时隔很久的一点题目总结