深度优先搜索 Depth First Search DFS

深度优先是比较基础的一种方法，还有一种是它的兄弟广度优先
深度优先顾名思义：先深入搜索到一种情况的"底部"（原谅我用了这么抽象的词），然后再返回搜索其它情况

例题

我们依旧举例说明，比如我们现在想要在A,B,C三个箱子中放入1,2,3三张牌，想知道一个有多少种情况

循环举穷

首先我们一步步尝试每一次，每一个箱子中的放牌情况
我们约定，对于每个箱子，我们都优先放入1，然后是2，最后是3
当然，如果手上一张牌都没有，也就说明某种情况被列举完了
我们用一个数组a代表箱子，step代表第step个箱子，而i代表牌
我们利用下面这个循环来进行举穷

    for(i = 1;i<=n:i++ ){
        a[step] = i ;
    }

另外，一张牌只能用一次，因此我们还要加入一个标记数组book
我们约定： book[i]= 0 代表牌还在手上，=1代表用掉了

所以，我们能把代码更新为：

    for(i = 1;i<=n:i++ ){
        if(book[i] == 0 ){
            a[step] = i ; //将i号扑克牌放入第step个箱子中
            book[i] = i ; //将book[i] 设为1，代表我们的i号扑克已经不在手上了
        }
    }

方法与递归

我们观察整体的解法已经上述的举穷，不难发现：我们想要的搜索，实质上就是不断使用上面的方法
所以，我们处理每个盒子的方法都是一样的，我们之间把上述代码变成方法

    void dfs(int step){
        //step是箱子处理第step个箱子

        for(i = 1;i<=n:i++ ){
            if(book[i] == 0 ){
            a[step] = i ; //将i号扑克牌放入第step个箱子中
            book[i] = i ; //将book[i] 设为1，代表我们的i号扑克已经不在手上了
        }
    }

        return ; 
    }

我们不断按顺序处理下去，每次都在方法中调用方法自身并把参数加一，我们把这样的做法叫递归
另外，每一个箱子尝试之后，记得收回牌

事实上，开始“收牌”就意味着某一次的情况已经被举完了

    void dfs(int step){
        //step是箱子处理第step个箱子

        for(i = 1;i<=n:i++ ){
            if(book[i] == 0 ){
            a[step] = i ; //将i号扑克牌放入第step个箱子中
            book[i] = i ; //将book[i] 设为1，代表我们的i号扑克已经不在手上了
            dfs(step+1);  //递归
            book[i] = 0 ; //收牌
        }
    }

        return ; 
    }

收尾

那么我们的搜索什么时候是个头呢，也就是我们搜到第n+1个盒子的时候
（因为卡牌数量和盒子是对应的，循环中n代表有几张牌）

所以，处理到第n+1个盒子时，我们就打印出放法，然后return

P.S 不return就死循环了

完整的方法代码如下：

    void dfs(int step){
        if(step == n+1){
            //放好牌的情况
            for(i=1;i<=n;i++)
                printf("%d",a[i]);
            printf("\n");

            return ; 
        }


        //step是箱子处理第step个箱子

        for(i = 1;i<=n:i++ ){
            if(book[i] == 0 ){
            a[step] = i ; //将i号扑克牌放入第step个箱子中
            book[i] = i ; //将book[i] 设为1，代表我们的i号扑克已经不在手上了
            dfs(step+1);  //递归
            book[i] = 0 ; //收牌
            }
        }
        return ; 

    }

完整代码

    #incluide 

    int a[10],book[10],n ; 

        void dfs(int step){
        if(step == n+1){
            //放好牌的情况
            for(i=1;i<=n;i++)
                printf("%d",a[i]);
            printf("\n");

            return ; 
        }


        //step是箱子处理第step个箱子

        for(i = 1;i<=n:i++ ){
            if(book[i] == 0 ){
            a[step] = i ; //将i号扑克牌放入第step个箱子中
            book[i] = i ; //将book[i] 设为1，代表我们的i号扑克已经不在手上了
            dfs(step+1);  //递归
            book[i] = 0 ; //收牌
            }
        }
        return ; 

    }

    int main(){
        scanf("%d",&n);
        dfs(1);
        getchar();getchar();
        return 0 ;
    }

小结

理解深度优先搜索的关键在于解决当下该如何做以及下一步如何做的内容
而“下一步如何做”往往可以利用循环或递归解决
我们可以把深度优先算法的模型概括为：

    void dfs(int step){
        判断边界
        尝试每一种可能 for(i=1;i<=n;i++)
        {
            继续下一步做啥 dfs(step+1) ; 
        }
        返回 
    }

深度优先算法————迷宫

我们尝试把深度优先算法应用到迷宫求解路径中去
实质上，很多搜索算法都是为这种事情服务的。
另外在寻路方面还有一位大佬，那就是A*，这是后话了

例题

我们假设迷宫由n行m列的格子组成，每个格子要么是空地要么是障碍物
设我们的终点在(p,q)，而起点在(1,1)，寻找两点之间的最短路径
(设n,m均小于50)

思路

首先明确人和计算机是不一样，我们最重要的就是找一个通用的搜索法，然后一直用它直到结束
我们需要约定一个顺序进行搜索，并且它是可以运用于每一个格子的
我们不妨这么干：
1.按照右，下，左，上的顺序进行尝试
2.检测：障碍物无法到达，不可越界，不要去走过的点
3.下一点

另外，在每次行动的开始，我们还要判断一件事，那就是是否到达了终点

终点检测

那么这么一个函数只需要三个参数： x,y,总步数

    void dfs(int x, int y, int step){
        //判断是否到达目标点  
        if(x==p && y==q){
            //检测是不是新的最小值
            if(step < min)      min = step ; 

            return ; //无论如何记得return哦，因为这是我们的base case
        }
    }

顺时针尝试

我们利用一个数组来进行“尝试”的描述

    int next[4][2] = {  {0,1},  //向右
                        {1,0},  //向下
                        {0,-1}, //向左
                        {-1,0}  //向上},

为什么这么设计呢，我们不妨把这个数组想象为一个向量
对于我们的地图(它实质也是一个二维数组)而言，下标的增加代表向右/向下，减少则是向左/向上
因此在之后的计算中，利用next数组可以迅速得到下一个点的坐标

我们再加上一个for循环来枚举所有可能，就可以得到一个尝试的枚举

    for(k=0;k<=3;k++){
        tx = x + next[k][0];
        ty = y + next[k][1];
    }

这一部分要是觉得太抽象了，可以画一下next数组的样子来理解，有空的话这里会补图

检测：哪些地方不能去

主要进行下面三个判断：
1.是否越界。根据tx,ty的数值以及地图大小判断即可
2.是否为障碍物。设置一个数组a来登记障碍物
3.是否已经走过。设置一个标记数组book进行标记

可能有人会提出：把走过的路加到障碍物数组中就行了，这种想法很好但实际上却是不方便的
book数组的意义有两个，一是标记走过的路，二是配合尝试计算多个路径（类比一下之前的拿牌和收回牌）

这部分的判断如下：

    if(tx<1 || tx>n || ty<1 || ty>m ){
        continue ; //continue就是跳过其它步骤直接进入下一次循环。因为这个点越界了啊
    }

    if(a[tx][ty]==0 && book[tx][ty]==0){
        //如果障碍物数组a和标记数组book都没标记过这个点
        book[tx][ty]=1 ; //标记该路径已走过
        dfs(tx,ty,step+1) ; //利用递归进行下一步
        book[tx][ty]=0 ; //某次尝试的结束，我们要拿回标记

        /*
        另外，这里就不要continue了，反正都是最后一步了(或者不会执行这一步)
        book[tx][ty]=0作为递归部分的下一步，实质上代表了某次尝试的结束
        */
    }

完整代码

    #include
    
    int n,m,p,q,min = 9999999 ; 

    int a[51][51] , book[51][51] ; 

    void dfs(int x, int y ,int step){
        int next[4][2] = {  {0,1},  //向右
                            {1,0},  //向下
                            {0,-1}, //向左
                            {-1,0}  //向上
                            };

        int tx,ty,k ; 

        //判断是否到达目标点  
        if(x==p && y==q){
            //检测是不是新的最小值
            if(step < min)      min = step ; 

            return ; //无论如何记得return哦，因为这是我们的base case
        }

        //枚举走法
        for(k=0;k<=3;k++){
            tx = x + next[k][0];
            ty = y + next[k][1];

            if(tx<1 || tx>n || ty<1 || ty>m ){
                continue ; //continue就是跳过其它步骤直接进入下一次循环。因为这个点越界了啊
            }

            if(a[tx][ty]==0 && book[tx][ty]==0){
                //如果障碍物数组a和标记数组book都没标记过这个点
                book[tx][ty]=1 ; //标记该路径已走过
                dfs(tx,ty,step+1) ; //利用递归进行下一步
                book[tx][ty]=0 ; //某次尝试的结束，我们要拿回标记

                /*
                另外，这里就不要continue了，反正都是最后一步了(或者不会执行这一步)
                book[tx][ty]=0作为递归部分的下一步，实质上代表了某次尝试的结束
                */
            }
        }
        return ; 
    }


    //主函数 
    int main(){
        int i,j,startx,starty;

        //读入相关数值
        scanf("%d %d",&n,&m) ; //地图大小

        //读入障碍物
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                scanf("%d" , &a[i][j]) ;
            }
        }

        //读入起点和终点 
        scanf("%d %d %d %d",&startx,&starty,&p,&q);

        //开始设置
        book[startx][starty] = 1;

        //开始搜索
        dfs(startx,starty,0) ; 

        //输出最短步数
        printf("%d" , min);

        getchar();getchar();
        return 0 ;
    }