算法文章---深搜

———————————————深搜———————————————
深搜也叫深度优先搜索意思是就是一直向前进，直到走不动了，向后退一步，继续前进。这个叫做不撞南墙不回头。

深搜也是dfs：而dfs就像有n个阶段，第n个阶段走不通，就回退到第n-1个阶段尝试其他的可能。
-----  
DFS：  void dfs(int step){  
           ---->判断边界   
        if(...) return;
            ---->尝试每一种可能
           for(int i=1;i<=n;i++){   
           ...   
           ...   
        ---->继续下一步      
        dfs(step+1);   
        }
}
----
dfs可以解决许多问题比如：数字排列类
（1）排列型枚举：这就是全排列问题
代码实现可以是这样：
#include<bits/stdc++.h>
using namespace std;
int n,a[10],book[10];
void dfs(int x){   //正在第x个格子
        if(x>n){    //如果已经放完最后一个格子
                for(int i=1;i<=n;i++){                        
                        printf("%5d",a[i]);  //输出已经放好的数字
                }               
                cout<<endl;       
        }else{   //否则继续挑数                
                for(int i=1;i<=n;i++){    //挑选的范围就是1-n        
                        if(book[i]==0){     //如果i没有被用过                                
                                book[i]=1;      //标记i被用过        
                                a[x]=i;         //将i放进a数组的第x个格子
                                dfs(x+1);       //继续搜索下一个格子                                                                 book[i]=0;      //回溯  把i还回去                         }                                        }       
                        }
                }
int main(){       
        cin>>n;        dfs(1);    //从第1个格子开始放数       
        return 0;
}
第二种组合型枚举：
#include<bits/stdc++.h>
using namespace std;
int n,a[30],book[30],f[30],k,ans;int fun(int x){ //判断质数
        if(x==1) return 0;       
        for(int i=2;i<x;i++){       
                if(x%i==0) return 0;       
        }        
        return 1;
}
void dfs(int x){  //现在正在第几个格子
        if(x>k){  //不需要继续下一个格子        
        int s=0;               
        for(int i=1;i<=k;i++){               
                s+=a[i];       
        }                
        if(fun(s)==1){   //判断目前这种方案是否满足要求       
                ans++;               
        }        
        }else{   //往格子里面放数        
        for(int i=1;i<=n;i++){  //可选择的数字范围        
                if(book[i]==0){  //在f数组的第i个数字没有被用过                                                 book[i]=1;    //标记用过                                                                         a[x]=f[i]; // 将f[i]存放到数组a中
                dfs(x+1); //去下一个格子
                book[i]=0;  //回溯 把数字还回去
                }        
        }       
}
}int main(){       
        cin>>n>>k;       
        for(int i=1;i<=n;i++){       
        cin>>f[i];       
        }       
        dfs(1);   //从第一个格子开始       
        int c=1;       //组合数等于排列数除以 k的阶乘       
        for(int i=1;i<=k;i++){               
                c=c*i;       
        }       
        cout<<ans/c;
        return 0;
}
（3）迷宫类
求起点到终点：
#include<bits/stdc++.h>
using namespace std;
int mat[10][10],book[10][10];
int n,m,t,x,y,sx,sy,fx,fy,ans;
int b[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
void dfs(int x,int y){  //挑选下一个格子  （x,y）现在的位置        
        if(x==fx&&y==fy){ //到达终点        
                ans++;     //方案数加一       
        }else{   //要继续往后走                
                //四个方向：上下左右        
        for(int i=0;i<=3;i++){               
                int nx=x+b[i][0],ny=y+b[i][1]; //满足三个条件即为可以走       
                        if(mat[nx][ny]==0){    //一、不是障碍物       
                        if(book[nx][ny]==0){   //二、没有走过                                                                if(nx>=1&&nx<=n&&ny>=1&&ny<=m){  //三、没有超过地图边界                                                book[nx][ny]=1;    //标记此位置走过                                                                dfs(nx,ny);     //去往这个点继续走                                                                book[nx][ny]=0;   //从这个位置退回去                                                                }                       
                  }               
             }                
       }       
   }
}
int main(){       
        cin>>n>>m>>t;
        cin>>sx>>sy>>fx>>fy;       
        for(int i=1;i<=t;i++){       
                cin>>x>>y;               
                mat[x][y]=1;       
        }       
        book[sx][sy]=1;   //标记起点走过       
        dfs(sx,sy);    //从起点开始搜索       
        cout<<ans;       
        return 0;
}
（4）连通块类：
一个连通块就相当于一个迷宫，都是封闭的一块。但是不同的是，迷宫里设有障碍，连通块里没有，可以随意走，并且迷宫的搜索起点和搜索的终点都是确定好的，但连通块的起点可以是随便定的的，所以通常情况下需要遍历多个元素，寻找搜索起点，可能有多个起点。
#include<iostream>
using namespace std;
char mat[105][105];
int b[4][2]={1,0,0,1,-1,0,0,-1},n,m,ans;
void dfs(int x,int y){  //现在在(x,y)        
        for(int i=0;i<=3;i++){               
        int nx=x+b[i][0];       
        int ny=y+b[i][1];
        if(mat[nx][ny]!='0'&&nx>=1&&nx<=n&&ny>=1&&ny<=m){               
                mat[nx][ny]='0';  //将与它相邻的细胞都消掉
                dfs(nx,ny);               
          }       
        }
}int main(){       
        cin>>n>>m;       
        for(int i=1;i<=n;i++){               
                for(int j=1;j<=m;j++){               
                        cin>>mat[i][j];               
                }       
        }       
        for(int i=1;i<=n;i++){   //遍历每一个元素       
                for(int j=1;j<=m;j++){                       
                        if(mat[i][j]!='0'){  //找到一个非零元素就开始搜索                
                                mat[i][j]='0';   //将和它连在一起的所有非零元素都标记掉，避免重复计算                                ans++;   //细胞数量加一        
                                dfs(i,j);                
                        }       
                }       
        }       
        cout<<ans;        
        return 0;
}