Lake Counting

 

试题描述

有一个大小为M*N的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里共有多少水洼？（八连通指的是下面图中相对W的*的部分）
***
*W*
***
限制条件：
N,M≤100

输入

第一行包含两个正整数 N 和 M，表示将一个园子地面分成N*M块方格，N 行，M列，接下来的 N 行描述了园子地面状况，其中‘W’表示积水的水洼，‘.’表示没有积水。

输出

仅一个数，表示水洼的总数。

输入示例

10 12
w........ww.
.www.....www
....ww...ww.
.........ww.
.........w..
..w......w..
.w.w.....ww.
w.w.w.....w.
.w.w......w.
..w.......w.

输出示例

3

其实就是八连块。用dfs（即深度搜索）可以解决。

#include <iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
char mp[111][111];
int n,m;
int ans;
void dfs(int x,int y)
{
    mp[x][y]='*';
    for(int i=-1; i<=1; i++)
        for(int j=-1; j<=1; j++)
        {
            int xt=x+i;
            int yt=y+j;
            if(xt>=0&&xt<n&&yt>=0&&yt<m&&mp[xt][yt]=='W')
            {
                dfs(xt,yt);
            }
        }
    return;

}
int main()
{
    scanf("%d%d",&n,&m);
    if(n==0&&m==0)
        return 0;
    int ans=0;
    for(int j=0; j<n; j++)
        scanf("%s",mp[j]);
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(mp[i][j]=='W')
            {
                dfs(i,j);
                ans++;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}