AcWing 1097 池塘计数 flood fill bfs搜索

代码

#include <bits/stdc++.h>
using namespace std;const int N = 1010, M = N * N;typedef pair<int, int> PII;int n, m;char g[N][N];
bool st[N][N];
PII q[M];void bfs (int xx, int yy)
{int hh = 0, tt = -1;q[ ++ tt] = {xx, yy};st[xx][yy] = true;while (hh <= tt){int tx = q[hh].first, ty = q[hh].second;hh ++;for (int i = max(0, tx - 1); i <= min(n - 1, tx + 1); i ++ )for (int j = max(0, ty - 1); j <= min(m - 1, ty + 1); j ++ ){if (!st[i][j] && g[i][j] == 'W'){st[i][j] = true;q[ ++ tt] = {i, j};}}}
}int main()
{scanf("%d%d", &n, &m);for (int i = 0; i < n; i ++ ){scanf("%s", g[i]);}int ans = 0;for (int i = 0; i < n; i ++ )for (int j = 0; j < m; j ++ )if (g[i][j] == 'W' && !st[i][j]){
//				cout << i << " " << j << endl;bfs(i, j);ans ++;}printf("%d", ans);return 0;
}