池塘 flood fill
作者:
恒_41
,
2024-04-20 12:23:17
,
所有人可见
,
阅读 2
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010, M = N * N;
#define x first
//define 不加分号
#define y second
char g[N][N];
typedef pair<int, int> PII;
PII q[M];
bool st[N][N];
int n, m;
void bfs(int sx,int sy) {
int hh = 0;
int tt = 0;
q[0] = { sx,sy };
st[sx][sy] = true;//队头元素入队,标记
while (hh <= tt) {//hh<=tt队列非空tt指向队尾元素
PII 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 < 0 || i >= n || j < 0 || j >= m) continue;//越界
if (st[i][j] || g[i][j] == '.') continue;//已遍历的水洼或陆地
if (t.x == i && t.y == j) continue;//中心
q[++tt] = { i,j };//q[++tt]出队
st[i][j] = true;//标记
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> g[i];
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!st[i][j] && g[i][j] == 'W') {
bfs(i, j);
cnt++;
}
}
}
cout << cnt << endl;
return 0;
}