AcWing 1097. 池塘计数
原题链接
简单
作者:
十六
,
2021-01-12 15:45:16
,
所有人可见
,
阅读 253
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e3+10;
typedef pair<int, int> PII;
int n, m;
int ans;
char g[MAX][MAX];
bool v[MAX][MAX];
PII q[MAX*MAX];
void bfs(int r, int c){
int hh = 0, tt = 0;
v[r][c] = true;
q[0] = {r, c};
while(hh<=tt){
PII t = q[hh++];
for(int i=-1; i<2; i++){
for(int j=-1; j<2; j++){
if(i==0 && j==0) continue;
int rr = t.first+i, cc = t.second+j;
if(rr<0 || rr>=n || cc<0 || cc>=m) continue;
if(g[rr][cc]=='.' || v[rr][cc]) continue;
q[++tt] = {rr, cc};
v[rr][cc] = true;
}
}
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i=0; i<n; i++) scanf("%s", g[i]);
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(!v[i][j] && g[i][j]=='W'){
bfs(i, j);
ans++;
}
}
}
cout<< ans<< endl;
return 0;
}