计蒜客踏青 dfs

系统管理员 2022-01-06 11:47 247阅读 0赞

题目：

https://www.jisuanke.com/course/2291/182234

思路：

紫书P163联通块问题。

1.遍历所有块，找到草地，判断合法性，合法其id值加一，最后加出来的id值就是联通块的数量。

2.注意结束条件，先判断是否结束dfs，再给vis赋值。

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstdlib>
     4 #include<cstring>
     5 using namespace std;
     6 //求联通块，紫书P163
     7 
     8 int di[4][2]={
        {-1,0},{
        0,1},{
        1,0},{
        0,-1}};
     9 int id;
    10 int n,m,ex,ey,sx,sy;
    11 char maze[101][101];
    12 int vis[101][101];
    13 
    14 bool judge(int x,int y)//判断合法性，合法：没有越界，没有被访问(vis==0)，是草地(#) 
    15 {
    16     if(x>=0&&x<=n-1&&y>=0&&y<=m-1&&vis[x][y]==0&&maze[x][y]=='#')
    17     return true;
    18     return false;
    19 } 
    20 
    21 void dfs(int x,int y,int id)
    22 {
    23     
    24 //    printf("x=%d y=%d id=%d\n",x,y,id);
    25     if(!judge(x,y))
    26     {
    27         //printf("maze[%d][%d]=%c\n",x,y,maze[x][y]);
    28         return;
    29     }
    30     vis[x][y]=id;
    31     for(int i=0;i<4;i++)//四个方向 
    32     {
    33         int nextx=x+di[i][0];
    34         int nexty=y+di[i][1];
    35         
    36         if(judge(nextx,nexty))
    37         {
    38             dfs(nextx,nexty,id);    
    39         } 
    40     }
    41 }
    42 int main()
    43 {
    44     while(scanf("%d%d",&n,&m)==2)
    45     {
    46         for(int i=0;i<n;i++)
    47         scanf("%s",maze[i]);
    48         memset(vis,0,sizeof(vis));
    49         id=0;
    50         for(int i=0;i<n;i++)
    51         {
    52             for(int j=0;j<m;j++)
    53             {
    54                 if(judge(i,j))
    55                 {
    56                     dfs(i,j,++id);
    57                 }
    58             }
    59         }
    60         printf("%d\n",id);
    61 //        for(int i=0;i<n;i++)
    62 //        {
    63 //            for(int j=0;j<m;j++)
    64 //            {
    65 //                printf("%d ",vis[i][j]);
    66 //            }
    67 //            printf("\n");
    68 //        }
    69     }
    70     return 0;
    71 }

转载于:https://www.cnblogs.com/fudanxi/p/10612286.html