DFS(深度优先搜索)

前言

DFS这个算法呢，在我理解里算是一种暴力的算法，他把所有的可能性都遍历了一次。
做法也挺简单的，首先，不管不顾，一直往下找，然后到了边界或者找到了答
案就进行回溯。
这里比较难的就是回溯的理解和实现，刚开始多用纸推导吧，非常有效的方法，再加上不断的调试。

例题

N皇后

http://acm.hdu.edu.cn/showproblem.php?pid=2553

1
2

在N * N的方格棋盘放置了Ñ个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

HDU 2553
先以N=8为例子

尝试在第一行摆放第一个皇后(绿色的是封锁区域)

尝试在第二行摆放第二个皇后

尝试在第三行摆放第三个皇后

尝试在第四行摆放第四个皇后

尝试在第五行摆放第五个皇后

这时候只放了五个皇后，但是已经没法放了，所以回到第四行，重新摆放第四个皇后到第七格。

然后以此类推，不断遍历。

下面说说如何实现

1.棋子摆放位置的记录
用一个一维数组记录
int sel[12]; //下标表示第几行，储存的数据代表列刚开始数组的值全部初始化为0
2.判断某个格子能不能放棋子(是不是绿色)
行列可以根据上面的数组来判断。
对角线的话，同一条对角线x-y是相同的，可以根据这个判断

#include <iostream>
#include <cmath>
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的应用不止于此，与其说它是一种算法，不如说是一种思想，一种遍历所有可能的思想。
下面贴两个常用的模板吧

递归
void f()
{
    if(符合边界条件)
    {
       ///////
        return;
    }
    //某种形式的调用
     f();
}
```c
void dfs(int 当前状态)
{
    if(当前状态为边界状态)
    {
        记录或输出
        return;
    }
    for(i=0;i<n;i++)	//横向遍历解答树所有子节点  
    {
        //扩展出一个子状态。
        修改了全局变量
        if(子状态满足约束条件)
        {
            dfs(子状态)
        }
        恢复全局变量//回溯部分
    }
}

上边的图来自公众号程序员小灰
里面挺多有趣的算法，大家可以去观摩观摩