AcWing 1097. 池塘计数
原题链接
简单
作者:
hai阿卢
,
2021-02-22 16:25:30
,
所有人可见
,
阅读 240
#include<iostream>
#include<queue>
using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
int n, m, cnt;
char a[N][N];
bool s[N][N];
queue<PII> q;
void BFS(int i, int j)
{
q.push({i,j});
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
s[i][j] == true;
while(!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int k = 0; k < 8; k++)
{
int xi = x + dx[k];
int yi = y + dy[k];
if(xi > 0 && xi <= n && yi <= m && yi >0 && a[xi][yi]=='W' && !s[xi][yi])
{
q.push({xi, yi});
s[xi][yi] = true;
}
}
}
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
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' && !s[i][j])
{
BFS(i,j);
cnt++;
}
}
}
cout << cnt << endl;
return 0;
}