AcWing 1097. 池塘计数
原题链接
简单
作者:
Value
,
2020-06-24 13:43:27
,
所有人可见
,
阅读 410
#include <iostream>
#include <queue>
using namespace std;
const int N = 1010;
char graph[N][N];
bool st[N][N];
typedef pair<int, int> pii;
int dic[8][2] = {
{-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
{0, 1}, {1, -1}, {1, 0}, {1, 1}
};
int n, m;
void bfs(int x, int y){
queue<pii> qu;
qu.push({x, y});
st[x][y] = true;
while(!qu.empty()){
pii now = qu.front();
qu.pop();
for(int i = 0; i < 8; i ++ ){
int xx = now.first + dic[i][0];
int yy = now.second + dic[i][1];
if(xx >= 0 && xx < n && yy >= 0 && yy < m && graph[xx][yy] == 'W' && !st[xx][yy]){
st[xx][yy] = true;
qu.push({xx, yy});
}
}
}
}
int main(){
cin >> n >> m;
int res = 0;
for(int i = 0; i < n; i ++ ) cin >> graph[i];
for(int i = 0; i < n; i ++ ){
for(int j = 0; j < m; j ++ ){
if(graph[i][j] == 'W' && !st[i][j]){
bfs(i, j);
res ++ ;
}
}
}
cout << res << endl;
return 0;
}