2520: 【普及-】【P1596】Lake Counting S
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：12
解决：6
题目描述
由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个 的网格图表示。每个网格中有水（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提示
#include<bits/stdc++.h>
using namespace std;
struct point{
int x,y;
};
int n,m,ans=0,dx[8]={0,-1,-1,-1,0,1,1,1},dy[8]={-1,-1,0,1,1,1,0,-1};
char land[105][105];
bool mark[105][105]={0};
queue<point> q;
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
cin>>land[i][j];
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(land[i][j]=='W'&&mark[i][j]==0) {
ans++;
mark[i][j]=1;
//bfs
q.push(point{i,j});
while(!q.empty()) {
point p=q.front();
q.pop();
for(int k=0;k<8;k++) {
int x=p.x+dx[k],y=p.y+dy[k];
if (x<0||y<0) continue;
if (land[x][y]=='W'&&mark[x][y]==0) {
mark[x][y]=1;
q.push(point{x,y});
}
}
}
}
}
}
cout<<ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0,dx[8]={0,-1,-1,-1,0,1,1,1},dy[8]={-1,-1,0,1,1,1,0,-1};
char land[105][105];
bool mark[105][105]={0};
void dfs(int x,int y) {
for(int i=0;i<8;i++) {
int tx=x+dx[i],ty=y+dy[i];
if(land[tx][ty]=='W'&&mark[tx][ty]==0) {
mark[tx][ty]=1;
dfs(tx,ty);
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
cin>>land[i][j];
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(land[i][j]=='W'&&mark[i][j]==0) {
ans++;
mark[i][j]=1;
dfs(i,j);
}
}
}
cout<<ans;
return 0;
}