有一个大小为 N \times MN×M 的园子,雨后发生积水。八连通的积水被认为是连接在一起的。
请求出园子中有多少个水洼?
何为八连通
***
*W*
***
对于 W 来说,* 就是八个与它连通的点
输入
- 第一行两个整数 N,M(1 \leq N,M \leq 100)N,M(1≤N,M≤100), 表示 NN 行 MM 列
- 接下来有 NN 行,每行 MM 个字符,可能是
.
,W
,.
表示地,W
表示水
输出
- 一个整数,表示多少个水洼
样例 1
输入
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
#include<bits/stdc++.h>
using namespace std;
int N,M;
char m[1001][1001];
void dfs(int x,int y)
{
m[x][y]='.';
for(int dx=-1;dx<=1;dx++)
for(int dy=-1;dy<=1;dy++)
{
if(m[x+dx][y+dy]=='W'&&(x+dx)>=0&&(y+dy)>=0)
{
dfs(x+dx,y+dy);
}
}
}
int main()
{
cin>>N>>M;
int count=0;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
cin>>m[i][j];
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
if(m[i][j]=='W')
{
dfs(i,j);
count++;
}
cout<<count<<endl;
}