再附上一篇DFS详解的，不明白DFS原理的同学可以看一看：
https://blog.csdn.net/li_jeremy/article/details/83714298
以下是全网收集整理的和自己写的部分，绝对保证dfs轻松入门。
核心代码：
关于dfs参数问题，什么在变化，就把什么设置成参数。
void dfs()//参数用来表示状态
{
if(到达终点状态)
{
…//根据题意添加
return;
}
if(越界或者是不合法状态)
return;
if(特殊状态)//剪枝
return ;
for(扩展方式)
{
if(扩展方式所达到状态合法)
{
修改操作;//根据题意来添加
标记；
dfs（）；
(还原标记)；
//是否还原标记根据题意
//如果加上（还原标记）就是 回溯法
}
}
}
为什么有的时候得要标记，因为这可以防止打转现象的发生，你可以想象如果没有标记，你在迷宫围绕着某条路径打转
但有的时候需要标记却不需要还原标记，为何不需要还原标记，不还原的意义是防止下次递归时走到已走过的位置，还原是可 以让下次递归可以在经过原先递归走过的路径，当然不可能和原先一模一样的路径
DFS全排列
#include<iostream>
using namespace std;
int n;
int book[10] = {0};
int a[10];
void dfs(int index)
{
if(index == n) //递归终止条件
{
for(int i = 0;i < n;++i)
cout << a[i];
cout << endl;
return ;
}
else
{
for(int i = 1;i <= n;++i)
{
if(!book[i])
{
book[i] = 1;//标记位
a[index] = i;//把符合的数字保存到数组中
dfs(index+1);
a[index] = 0;
book[i] = 0;//还原标记，以便回溯
}
}
}
}
void init()
{
for(int i = 0;i < 9;++i)
book[i] = 0;
}
int main()
{
while(cin >> n)
{
dfs(0);
init();
}
return 0;
}
方格填数
如下的10个格子
+–+–+–+
| | | |
+–+–+–+–+
| | | | |
+–+–+–+–+
| | | |
+–+–+–+
（如果显示有问题，也可以参看【图1.jpg】）
填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
这就是道全排列的变式题(因为数字是0-9，且填入到格子中)，因为它必须去检查所填的数字是否符合题目要求
思路：明显这是回溯题，可以用dfs做，当然你也可以套10个循环来做（TLE）
dfs的话这道题我们该如何进行递归，很明显这道题和全排列类似，所以我们可以一个方格一个方格来填空
由于题意要求连续的两个数字不能相邻
所以需要判断/
左，上，左上，右上
/，因为在你下面和右面的都还没填呢
#include<iostream>
#include<cmath>
#include<sstream>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int ans = 0;
int dir[4][2] = {0,-1,-1,0,-1,-1,-1,1};
int book[10][10];
int a[10][10];
int vis[10];
/*左，上，左上，右上*/
bool check(int r,int c,int val)
{
for(int k = 0;k < 4;++k)
{
int tr = r + dir[k][0];
int tc = c + dir[k][1];
if(tr < 1 || tc < 1 || tr > 3 || tc > 4) continue;
if(abs(a[tr][tc]-val) <= 1) return false;
}
return true;
}
void dfs(int row,int col)
{
if(row == 3 && col == 4)
{
ans++;
return ;
}
if(col == 5)
{
row += 1;
col = 1;
}
for(int i = 0;i <= 9;++i)
{
if(!book[row][col] && !vis[i] && check(row,col,i))
{
book[row][col] = 1;
vis[i] = 1;
a[row][col] = i;
dfs(row,col+1);
book[row][col] = 0;
vis[i] = 0;
a[row][col] = -2;
}
}
}
int main()
{
for(int i = 0;i <= 5;++i)
{
for(int j = 0;j <= 9;++j)
a[i][j] = -2;
}
dfs(1,2);
printf("%d\n",ans);
return 0;
}
寒假作业
现在小学的数学题目也不是那么好玩的。
看看这个寒假作业：
□ + □ = □
□ – □ = □
□ × □ = □
□ ÷ □ = □
(如果显示不出来，可以参见【图1.jpg】)
每个方块代表1~13中的某一个数字，但不能重复。
比如：
6 + 7 = 13
9 – 8 = 1
3 * 4 = 12
10 / 2 = 5
以及：
7 + 6 = 13
9 – 8 = 1
3 * 4 = 12
10 / 2 = 5
就算两种解法。（加法，乘法交换律后算不同的方案）
你一共找到了多少种方案？
同样是全排列变式题，
思路：一个一个填，递归的参数应该是下标，用一维数组来存储，一种做法是，把加减乘除比较，不符合则返回上一层，还有一种做法，把12个位置先填满，在判断是否符合条件，这样做，时间复杂度更高
#include<iostream>
#include<cmath>
#include<sstream>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int ans = 0;
int vis[10];
int a[13];
void dfs(int index)
{
if(index == 13)
{
//为何不能a[10]/a[11] && a[10] % a[11] == 0， 11/5 == 2吧
if(a[10] == a[11]*a[12])
{
ans++;
}
return ;
}
//+
if(index == 3)
{
if(!vis[a[1]+a[2]])
{
vis[i] = 1;
a[index] = i;
dfs(index+1);
vis[i] = 0;
a[index] = 0;
}
return ;
}
//-
if(index == 7)
{
if(a[4]-a[5] != a[6])
return ;
}
//*
if(index == 10)
{
if(a[7]*a[8] != a[9])
return ;
}
for(int i = 1;i <= 13;++i)
{
if(!vis[i])
{
vis[i] = 1;
a[index] = i;
dfs(index+1);
vis[i] = 0;
a[index] = 0;
}
}
}
int main()
{
dfs(1);
printf("%d\n",ans);
return 0;
}
剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路：也是一道全排列变式题，只不过这里我们只截取其中5个格子判断是否连通，把选中的五个棋子的位置保存起来，如何判断连通呢？回溯即可
/*#include<iostream>
#include<cmath>
#include<sstream>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int ans = 0;
int vis[9][9];
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
int book[10000][5][5];
bool check(int count)
{
if(count == 0) return true;
for(int k = 0;k < count;++k)
{
int flag = 1;
for(int i = 1;i <= 3;++i)
{
for(int j = 1;j <= 4;++j)
{
if(book[k][i][j] != vis[i][j]) flag = 0;
}
}
if(flag)
return false;
}
return true;
}
void add(int a[][9],int count)
{
for(int i = 1;i <= 3;++i)
{
for(int j = 1;j <= 4;++j)
{
book[count][i][j] = vis[i][j];
}
}
}
void dfs(int r,int c,int sum)
{
if(sum == 4)
{
if(check(ans))
{
add(vis,ans);
ans++;
for(int i = 1;i <= 3;++i)
{
for(int j = 1;j <= 4;++j)
{
printf("%d ",vis[i][j]);
}
printf("\n");
}
printf("----------------------------------------------\n");
}
return ;
}
for(int k = 0;k < 4;++k)
{
int tr = r + dir[k][0];
int tc = c + dir[k][1];
if(tr < 1 || tc < 1 || tr > 3 || tc > 4) continue;
if(!vis[tr][tc])
{
vis[tr][tc] = 1;
dfs(tr,tc,sum+1);
vis[tr][tc] = 0;
}
}
}
int main()
{
for(int i = 1;i <= 3;++i)
{
for(int j = 1;j <= 4;++j)
{
if(!vis[i][j])
{
vis[i][j] = 1;
dfs(i,j,0);
vis[i][j] = 0;
}
}
}
printf("%d\n",ans);
return 0;
}*/
//别人的做法
#include<iostream>
#include<cmath>
#include<sstream>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int ans = 0;
int que[13][2]; //保存信息
int book[13][13];
int a[10];
int vis[14];
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
int flag = 1;
//通过回溯来判断
int check(int x,int y)
{
if(book[x][y] == 0) return 0;
book[x][y] = 0;
return 1+check(x-1,y)+check(x+1,y)+check(x,y-1)+check(x,y+1);
}
void dfs(int sum,int last)
{
if(sum == 5)
{
memset(book,0,sizeof(book));
//这里如何去判重
for(int i = 0;i < 5;++i)
{
book[que[a[i]][0]][que[a[i]][1]]= 1;
}
flag = 1;
if(check(que[last][0],que[last][1]) == 5)
{
ans++;
}
return ;
}
for(int i = last+1;i <= 12;++i)
{
if(!vis[i])
{
vis[i] = 1;
a[sum] = i;
dfs(sum+1,i);
vis[i] = 0;
a[sum] = -1;
}
}
}
int main()
{
int n = 1;
for(int i = 1;i <= 3;++i)
{
for(int j = 1;j <= 4;++j)
{
//保存每个方格的横纵坐标
que[n][0] = i;
que[n++][1] = j;
}
}
dfs(0,0);
printf("%d\n",ans);
return 0;
} 初学dfs：先做最最最基础的题： http://codeup.cn/contest.php?cid=100000608。
做完了，你就入门了（绝对没有比这更基础的题了）
然后再做下面的题：
题型分类：
写过这些入门题后，我们可以将DFS题分为两大类：
1 . 地图型：这种题型将地图输入，要求完成一定的任务。因为地图的存在。使得题意清楚形象化，容易理清搜索思路。
POJ 1031棋盘问题
（类似八皇后问题）http://poj.org/problem?id=1321
AOJ 869-迷宫(遍历地图，四向搜索)
https://blog.csdn.net/chen_yuazzy/article/details/73656668
HDU 1035-Robot Motion(指定方向搜索，迷路（循环）判断)
http://acm.hdu.edu.cn/showproblem.php?pid=1035
HDU 1045-Fire Net(check函数，回溯)
http://acm.hdu.edu.cn/showproblem.php?pid=1045
HDU 1010-Tempter of the Bone(奇偶剪枝，回溯)
http://acm.hdu.edu.cn/showproblem.php?pid=1010
2 . 数据型：这种题型没有给定地图，一般是一串数字或字母，要求按照一定的任务解题。相对于地图型，这种题型较为抽象，需要在数据中进行搜索。数据以数组的形式存储，那么只要将数组也当作一张图来进行搜索就可以了。
HDU 1016-Prime Ring Problem(回溯、素数筛)
HDU 1258-Sum It Up(双重DFS递归，去重技巧)
HDU 1015-Safecraker(回溯，字符处理)
HDU 2676-Sudoku(抽象，回溯)
以下是一些DFS：
Sticks
http://acm.hdu.edu.cn/showproblem.php?pid=1455
http://acm.hdu.edu.cn/showproblem.php?pid=1455
http://acm.hdu.edu.cn/showproblem.php?pid=2553
http://acm.hdu.edu.cn/showproblem.php?pid=1426
http://acm.hdu.edu.cn/showproblem.php?pid=1528
http://acm.hdu.edu.cn/showproblem.php?pid=1175
http://acm.hdu.edu.cn/showproblem.php?pid=1010
http://acm.hdu.edu.cn/showproblem.php?pid=1312
http://acm.hdu.edu.cn/showproblem.php?pid=1716
http://acm.hdu.edu.cn/showproblem.php?pid=5547
http://acm.hdu.edu.cn/showproblem.php?pid=1181
http://acm.hdu.edu.cn/showproblem.php?pid=5305
记忆化搜索（DFS+DP）：
http://acm.hdu.edu.cn/showproblem.php?pid=1978
http://acm.hdu.edu.cn/showproblem.php?pid=1078
http://acm.hdu.edu.cn/showproblem.php?pid=1428