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

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 55, M = N * N;

int n, m;
int g[N][N];   // 地图
PII q[M];      // 队列
bool st[N][N]; // 标识是否走过

int dx[] = {0, -1, 0, 1}; // 左上右下
int dy[] = {-1, 0, 1, 0}; // 西北东南 1 2 4 8 二进制位运算，参考1098_0.cpp

int bfs(int sx, int sy) {
    int hh = 0, tt = -1;
    q[++tt] = {sx, sy};
    st[sx][sy] = true;

    // 一次bfs跑一个连通块，统计一个连通块的面积
    int area = 1; // 既然能入队列，最起码有入口房间，是一个面积

    while (hh <= tt) {
        PII t = q[hh++];
        for (int i = 0; i < 4; i++) {
            int tx = t.x + dx[i], ty = t.y + dy[i];
            if (tx == 0 || tx > n || ty == 0 || ty > m) continue;
            if (st[tx][ty]) continue;
            // 1表示西墙，2表示北墙，4表示东墙，8表示南墙
            if (g[t.x][t.y] >> i & 1) continue; // 前进的方向上有墙
            // 连通的房间入队列
            q[++tt] = {tx, ty};
            st[tx][ty] = true;
            area++; // 入队列时房间面积++
        }
    }
    return area;
}
int cnt, area; // 房间数，最大面积
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 (!st[i][j]) {
                // 从此点出发找连通块
                area = max(area, bfs(i, j));
                cnt++; // 记录连通块个数
            }

    printf("%d\n%d\n", cnt, area);
    return 0;
}