POJ2386 Lake counting

2019/7/22 18:01:23 人评论 次浏览 分类:学习教程

Lake counting 深度优先搜索的简单应用

所谓深度优先搜索是指从最初的状态出发,遍历所有可能达到的状态。由此可以对所有状态进行操作,或者枚举出所有状态

题目大意

给一个m*n 的园子,找出其中有多少处水洼,其中那种八连通的水洼是算作一处(该水洼周围一圈都看作连起来的)
W W W
W M W 像这样的就算做一处
W W W
Sample Input1
0 12
样例
output
3

解题思路

遍历每一个点,遍历的时候,如果该点为W就把该点及周围的所有W变成 . ,同时计数器加一,最终输出计数器的值。这里用函数递归实现

解题代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
char a[102][102];
int m,n;
void dfs(int x,int y)
{
   int p,q;
   for(int i=-1;i<=1;i++)
   {
       for(int j=-1;j<=1;j++)
       {
           p=x+i;
           q=y+j;
           if(p<n&&p>=0&&q<m&&q>=0&&a[p][q]=='W')
           {
                 a[p][q]='.';
                 dfs(p,q);
           }

       }
   }
}
int main()
{


   while(~scanf("%d %d",&n,&m))
   {
       for(int i=0;i<n;i++)
   {
       for(int j=0;j<m;j++)
       {
           cin>>a[i][j];
       }

   }
   int b=0;
   for(int i=0;i<n;i++)
   {
       for(int j=0;j<m;j++)
       {
           if(a[i][j]=='W')
           {
               b++;
               dfs(i,j);

           }
       }

   }
   cout<<b<<endl;
   }

    return 0;
}

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->