python/TangDou/AcWing/FloodFill/1097_bfs.cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = N * N;

typedef pair<int, int> PII;
#define x first
#define y second

// 方向数组
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, -1, 1};

int n, m;
char g[N][N];

int ans;

PII q[M];
// 宽搜
void bfs(int sx, int sy) {
    int hh = 0, tt = -1;

    q[++tt] = {sx, sy}; // 起点入队列
    g[sx][sy] = '.';    // 标识为已使用过,防止回头路

    while (hh <= tt) {
        PII t = q[hh++]; // 一边取队列头，一边出队列
        for (int i = 0; i < 8; i++) {
            int tx = t.x + dx[i];
            int ty = t.y + dy[i];
            if (g[tx][ty] == 'W') {
                g[tx][ty] = '.';
                q[++tt] = {tx, ty};
            }
        }
    }
}
int main() {
    // n行m列　
    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') {
                bfs(i, j); // 开始宽搜
                ans++;     // 找到一块
            }
    printf("%d\n", ans);
    return 0;
}