AcWing 1097. 池塘计数
原题链接
简单
作者:
nocc
,
2024-05-19 18:49:48
,
所有人可见
,
阅读 2
#include <iostream>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1010, M = N * N;
int n, m, ans;
char g[N][N];
bool st[N][N];
PII q[M];
void bfs(int sx, int sy)
{
int hh = 0, tt = 0;
q[hh] = {sx, sy};
st[sx][sy] = true;
while (hh <= tt)
{
auto t = q[hh++];
for (int i = t.x - 1; i <= t.x + 1; i++)
{
for (int j = t.y - 1; j <= t.y + 1; j++)
{
if (i == t.x && j == t.y) continue;
if (i < 1 || i > n || j < 1 || j > m) continue;
if (g[i][j] == '.' || st[i][j]) continue;
q[++tt] = {i, j};
st[i][j] = true;
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> g[i][j];
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (g[i][j] == 'W' && !st[i][j])
{
bfs(i, j);
ans++;
}
}
}
cout << ans << endl;
return 0;
}