题解 P1596 【[USACO10OCT]湖计数Lake Counting】

Dream_It_Possible · 2017-07-10 09:15:26 · 题解

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath> 
#include<cstring>
using namespace std;
int a[200][200],n,m,ans,i,j;
char b;
void f(int x,int y)
{
    if (!a[x][y])
    return;
    a[x][y]=0;//符0，表示搜过，不在搜了。
    f(x-1,y);//向下。
    f(x+1,y);//向上。
    f(x,y-1);//向左。
    f(x,y+1);//向右。
    f(x-1,y-1);//向左上。
    f(x-1,y+1);//向右上。
    f(x+1,y-1);//向左下。
    f(x+1,y+1);//向右下。
        //共8个方向。
}
int main()
{
    cin>>n>>m;
    for (i=1;i<=n;i++)
    for (j=1;j<=m;j++)
    {
        cin>>b;
        if (b=='W')
        a[i][j]=1;//是水，转为1，方便后面计算
        else
        a[i][j]=0;//不是水，转为0，方便后面计算
    }
    for (i=1;i<=n;i++)
    for (j=1;j<=m;j++)
    {
        if (a[i][j])
        {
            ans++;//找到一个
            f(i,j);//以这一点去搜。
        }
    }
    cout<<ans;
    return 0;
}
//建议做完这题可以去看看P1451.