1409: 【例】【基础】数池塘（四方向）
内存限制：16 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：30
解决：17
题目描述
农夫约翰的农场可以表示成N*M（1≤N≤100≤M≤100）个方格组成的矩形。
由于近日的降雨，在约翰农场上的不同地方形成了池塘。
每一个方格或者有积水（'W'）或者没有积水（'.'）。
农夫约翰打算数出他的农场上共形成了多少池塘。
一个池塘是一系列相连的有积水的方格，每一个方格周围的四个方格都被认为是与这个方格相连的。
现给出约翰农场的图样，要求输出农场上的池塘数。
输入
第1行：由空格隔开的两个整数：N和M
第2..N+1行：每行M个字符代表约翰农场的一排方格的状态。
每个字符或者是'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.样例输出 复制
13提示
数据范围
。
#include<bits/stdc++.h>
using namespace std;
#define N 110
int n,m,c=0;
char a[N][N];
int fx[]={0,1,0,-1};
int fy[]={1,0,-1,0};
bool vis[N][N];
void dfs(int x,int y){
a[x][y]='.';
for(int i=0;i<4;i++){
int nx=x+fx[i],ny=y+fy[i];
if(a[nx][ny]=='W'){
dfs(nx,ny);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='W'){
c++;
dfs(i,j);
}
}
}
cout<<c;
}
#include<bits/stdc++.h>
using namespace std;
#define N 110
char a[N][N];
bool vis[N][N];
struct coord{
int x;
int y;
};
queue<coord> Q;
int n,m,sx,sy,ex,ey;
int dx[5]={0,0,1,0,-1};
int dy[5]={0,1,0,-1,0};
int cnt=0;
void bfs(int sx,int sy){
vis[sx][sy]=1;
coord tmp={sx,sy};
Q.push(tmp);
while(!Q.empty()){
coord u=Q.front();
int x=u.x,y=u.y;
Q.pop();
for(int i=1;i<=4;i++){
int tx=x+dx[i];
int ty=y+dy[i];
if(tx>=1&&ty>=1&&tx<=n&&ty<=m&&a[tx][ty]=='W'&&vis[tx][ty]!=1){
vis[tx][ty]=1;
coord tmp={tx,ty};
Q.push(tmp);
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='W'&&vis[i][j]!=1){
cnt++;
bfs(i,j);
}
}
}
cout<<cnt;
return 0;
}