前言
DFS这个算法呢，在我理解里算是一种暴力的算法，他把所有的可能性都遍历了一次。
做法也挺简单的，首先，不管不顾，一直往下找，然后到了边界或者找到了答
案就进行回溯。
这里比较难的就是回溯的理解和实现，刚开始多用纸推导吧，非常有效的方法，再加上不断的调试。
例题
N皇后
http://acm.hdu.edu.cn/showproblem.php?pid=25531
2在N * N的方格棋盘放置了Ñ个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
HDU 2553
先以N=8为例子
尝试在第一行摆放第一个皇后(绿色的是封锁区域)
尝试在第二行摆放第二个皇后
尝试在第三行摆放第三个皇后
尝试在第四行摆放第四个皇后
尝试在第五行摆放第五个皇后
这时候只放了五个皇后，但是已经没法放了，所以回到第四行，重新摆放第四个皇后到第七格。
然后以此类推，不断遍历。
下面说说如何实现
1.棋子摆放位置的记录
用一个一维数组记录int sel[12]; //下标表示第几行，储存的数据代表列 刚开始数组的值全部初始化为0
2.判断某个格子能不能放棋子(是不是绿色)
行列可以根据上面的数组来判断。
对角线的话，同一条对角线x-y是相同的，可以根据这个判断1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
using namespace std;
int sel[12]; //下标表示第几行，储存的数据代表列
int n,sum;
void dfs(int x) //这里的x代表行，y代表列
{
if(x > n) //当x大于n了，说明超过n*n棋盘的边界了，同时也说明n个棋子完美的放入到棋盘中，答案数加一
{
sum++;
return;
}
int i,y;
for(y=1;y<=n;y++) //把每一列的遍历一次
{
//检查对应位置能不能放
//首先检查竖直方向，横着的方向就不用检测了，因为是一行行来的
for(i=1;i<x;++i) //循环没有中断，表示选择的y没在1到x-1行使用过
{
if(y==sel[i])
break; //选择的y使用过了，结束遍历
}
if(i<x) //只有当i等于x时符合条件
continue; //i<x 表示选择的y已经在前面x-1行使用过了
//检查对角线
for(i=1;i<x;++i)
{
if(abs(sel[i]-y)==abs(i-x))
break;
}
if(i<x)//失败
continue;
sel[x]=y; //上边的都过了，表示在x行下此次选择的y可用
dfs(x+1); //进入下一行
}
return;
}
int main(int argc, char *argv[])
{
int i;
int result[12];
for(i=1;i<=10;i++) //打表，不然过不了
{
n = i;
sum =0;
memset(sel,0,sizeof(sel));
dfs(1);
result[i]=sum;
}
while(~scanf("%d",&i) && i!=0)
{
printf("%d\n",result[i]);
}
return 0;
}
这里得出的是方案的数量，其实完全可以修改成同时打印可行的方案
只要在dfs函数sum++后根据sel数组的信息打印出棋盘
总结
DFS的应用不止于此，与其说它是一种算法，不如说是一种思想，一种遍历所有可能的思想。
下面贴两个常用的模板吧1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30递归
void f()
{
if(符合边界条件)
{
///////
return;
}
//某种形式的调用
f();
}
```c
void dfs(int 当前状态)
{
if(当前状态为边界状态)
{
记录或输出
return;
}
for(i=0;i<n;i++) //横向遍历解答树所有子节点
{
//扩展出一个子状态。
修改了全局变量
if(子状态满足约束条件)
{
dfs(子状态)
}
恢复全局变量//回溯部分
}
}
上边的图来自公众号程序员小灰
里面挺多有趣的算法，大家可以去观摩观摩
