DFS

水深无声 2021-11-24 01:38 231阅读 0赞

DFS  
优先向搜索树深层搜索的搜索算法，对于一个合法的状态A，对于其所有的子状态（搜索树的儿子结点）选择一种进行探索  
递归这一过程，直至达到叶子结点或目前状态不合法则回溯至父亲结点，对另一种子状态进行搜索  
void DFS(状态A)\{  
      if(A不合法) return;//返回父亲结点或者不做任何操作   
      if(A为目标状态) 输出或者记录;  
      if(A不为目标状态) DFS(A+Δ);//递归调用搜索其中的一个子节点  
\}

可以不重不漏地枚举所有可能到达目标状态的路径

典型实例1——n皇后问题

1 #include<iostream>
     2 using namespace std;
     3 int n;//皇后的个数 
     4 int tot;
     5 int C[20];
     6 void search(int cur)
     7 {
     8     if(cur==n){
        //超出边界即放完了 
     9       for(int i=0;i<n;i++){
    10          for(int j=0;j<n;j++){
    11              if(C[i]==j) cout<<'*';
    12              else cout<<'o';
    13              if(j==n-1) cout<<endl;
    14          }
    15       } 
    16       cout<<endl;
    17       tot++;
    18     }
    19     else for(int i=0;i<n;i++)//列举列的数字 
    20         {
    21             int ok=1;
    22             C[cur]=i;//尝试把第cur行的皇后放在第i列 
    23             for(int j=0;j<cur;j++)
    24               if(C[cur]==C[j]||cur-C[cur]==j-C[j]||cur+C[cur]==j+C[j])
    25                  { 
    26                      ok=0;
    27                      break;
    28                  }
    29             if(ok) search(cur+1);     
    30         }
    31 }
    32 int main()
    33 {
    34     cin>>n;
    35     search(0);
    36     cout<<tot<<endl;
    37     return 0;
    38 }

典型实例2——马走日字

1 #include<iostream>
     2 using namespace std;
     3 int tot=0;
     4 int vis[5][5]={
        0};
     5 int Inboard(int x,int y){
        //判断位置x，y在不在棋盘中 
     6     if(x<5&&x>=0&&y<5&&y>=0) return 1;
     7     else return 0;
     8 }
     9 void DFS(int x,int y,int cur){
    10     if(Inboard(x,y)&&!vis[x][y]){
    11         cur++;
    12         vis[x][y]=cur;
    13         if(cur==25){
        //走满了 
    14             tot++;
    15             cout<<"Case#"<<tot<<endl;
    16             for(int i=0;i<5;i++){
    17                 for(int j=0;j<5;j++){
    18 //                    cout<<vis[i][j];
    19                     printf("%4d",vis[i][j]);
    20                     if(j==4) cout<<endl;
    21                 }
    22             } 
    23             cout<<endl;
    24             vis[x][y]=0;
    25             return;
    26         }
    27         else{
    28             DFS(x-1,y-2,cur);
    29             DFS(x-1,y+2,cur);
    30             DFS(x-2,y-1,cur);
    31             DFS(x-2,y+1,cur);
    32             DFS(x+1,y-2,cur);
    33             DFS(x+1,y+2,cur);
    34             DFS(x+2,y-1,cur);
    35             DFS(x+2,y+1,cur);
    36             vis[x][y]=0;
    37         }
    38     }
    39     else return;
    40 }
    41 int main(){
    42     DFS(0,0,0); 
    43     return 0;
    44 }

典型实例3——红与黑

问题描述：有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。（只能上下左右移动）

输入数据：包括多个数据集合。每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。 W 和 H 都不超过 20。在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下

1）‘ .’：黑色的瓷砖；

2）‘ \#’：红色的瓷砖；  
3）‘ @’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时，表示输入结束。

*输出要求：**对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。*

*输入样例**6 9*

*               ....\#.*

*               .....\#*

*               ......  
               ......  
               ......  
               ......  
               ......  
               \#@...\#  
               .\#..\#.  
              0 0  
输出样例 ：45*

1 #include<iostream>
     2 #include<string>
     3 #include<string.h>
     4 using namespace std;
     5 const int maxn=100;
     6 int n,m;//n是每行的个数，m是行数 
     7 string map[maxn+1];//地图 
     8 int vis[maxn+1][maxn+1];//标记数组 
     9 int cnt=0;//个数
    10 void DFS(int row,int col){
    11     if(row<0||row>=n||col<0||col>=m||vis[row][col]==true||map[row][col]=='#') return;//不合法 
    12     cnt++;
    13     vis[row][col]=true;
    14     DFS(row-1,col);
    15     DFS(row+1,col);
    16     DFS(row,col-1);
    17     DFS(row,col+1);
    18 }
    19 
    20 int main(){
    21     cin>>m>>n;//m是列数，n是行数 
    22     while(n||m){
    23         cnt=0;
    24         int row,col;//记录起始位置 
    25         for(int i=0;i<n;i++){
        //输入地图
    26             cin>>map[i]; 
    27             for(int j=0;j<m;j++){
    28                 if(map[i][j]=='@'){
    29                     row=i;
    30                     col=j;
    31                 }
    32             } 
    33         }
    34         memset(vis,0,sizeof(vis));//初始化
    35         DFS(row,col); 
    36         cout<<cnt<<endl;
    37         cin>>n>>m; 
    38     }
    39     return 0;
    40 }

典型实例4——找水洼八连格

1 #include<iostream>
     2 using namespace std;
     3 const int MAXN=100;
     4 const int MAXM=100;
     5 int N,M;
     6 char field[MAXN][MAXM];//园子 
     7 void dfs(int,int);
     8 void solve();
     9 int main()
    10 {
    11     cin>>N>>M;
    12     for(int i=0;i<N;i++)
    13        for(int j=0;j<M;j++)
    14            cin>>field[i][j];
    15     solve(); 
    16     return 0;
    17 }
    18 //现在位置（x，y） 
    19 void dfs(int x,int y)
    20 {
    21     field[x][y]='.';//将现在位置替换为.
    22     //循环遍历移动的8个方向 
    23     for(int dx=-1;dx<=1;dx++)
    24        {
    25               for(int dy=-1;dy<=1;dy++)
    26               {      
    27                      //向x方向移动dx，向y方向移动dy，移动的结果为（nx，ny） 
    28                         int nx=x+dx;
    29                         //判断（nx，ny）是不是在园子里，以及是否有积水 
    30                         int ny=y+dy;
    31                         if(0<=nx&&nx<N&&0<=ny&&ny<M&&field[nx][ny]=='W') dfs(nx,ny);
    32            }
    33        }
    34     return ;
    35 }
    36 void solve()
    37 {
    38     int res=0;
    39     for(int i=0;i<N;i++)
    40     {
    41         for(int j=0;j<M;j++)
    42              {
    43                  if(field[i][j]=='W') 
    44                  {   
    45                      //从有积水W的地方开始dfs 
    46                      dfs(i,j);
    47                      res++;
    48                 }
    49              }
    50     }
    51     cout<<res;
    52 }

小猫爬山（看似贪心，但是因为N非常小，用dfs）是纯正的dfs 八连格是变种

恢复现场：改变了什么要恢复什么

转载于:https://www.cnblogs.com/TYXmax/p/10989118.html