题目描述

农夫约翰有一片 N∗M 的矩形土地。

最近，由于降雨的原因，部分土地被水淹没了。

现在用一个字符矩阵来表示他的土地。

每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。

现在，约翰想知道他的土地中形成了多少片池塘。

每组相连的积水单元格集合可以看作是一片池塘。

每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。

请你输出共有多少片池塘，即矩阵中共有多少片相连的”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

其实这道题完全可以用深搜.
直接搜索每一个“ W ”周围是否还有“ W ”.
如果有，就将其变为“ . ”.
再统计答案即可.

时间复杂度 $O(我不知道)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,a[1010][1010];
char Map[1010][1010];
int dx[8]={1,0,-1,0,1,-1,1,-1},dy[8]={0,1,0,-1,1,-1,-1,1};//方向数组
void dfs(int x,int y)
{
    Map[x][y]='.';
    for(int i=0;i<8;i++)
        if(Map[x+dx[i]][y+dy[i]]=='W')
            dfs(x+dx[i],y+dy[i]);
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>Map[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(Map[i][j]=='W'){//找到“ W ”.
                dfs(i,j);
                ans++;//统计答案
            }
    printf("%d\n",ans);
    return 0;
}