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

#include <bits/stdc++.h>

using namespace std;

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

// 1表示西墙，2表示北墙，4表示东墙，8表示南墙

// 模拟向北和向东两个方向
int dx[] = {-1, 0}; // 向北走时，x-1,y不变；向东走时，x不变，y+1
int dy[] = {0, 1};
int dw[] = {2, 4}; // 2:北墙, 4:东墙

// 模拟向东和向南两个方向 也是可以的
// int dx[] = {0, 1}; //向东走时，x不变，y+1; 向南走时，x+1,y不变
// int dy[] = {1, 0};
// int dw[] = {4, 8}; // 4:东墙, 8：南墙

// 模拟向南向西 也是可以的
// int dx[] = {1, 0}; //向南走时，x+1,y不变；向西走时，x不变，y-1
// int dy[] = {0, -1};
// int dw[] = {8, 1}; // 8:南墙, 1:西墙

// 模拟向南向东 也是可以的
// int dx[] = {1, 0}; //向南走时，x+1,y不变；向东走时，x不变，y+1
// int dy[] = {0, 1};
// int dw[] = {8, 4}; // 8:南墙, 4:东墙

int n, m;        // n行m列
int g[N][N];     // 地图
int p[M], sz[M]; // 并查集数组，与并查集内成员个数
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

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 = 0; i < M; i++) p[i] = i, sz[i] = 1; // 每个人是自己的祖先，并且自己家族的成员数量为1

    int cnt = n * m, area = 1; // 总共最多有n*m个房间，最大面积最小是1

    // 开始从上到下，从左到右，枚举每个位置
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            // 探讨这个位置的房间，是不是能够向北和向东两个方向前进，也就是检查向北和向东是不是会遇到墙
            for (int u = 0; u < 2; u++)
                if (!(g[i][j] & dw[u])) {                             // 如果没有遇到墙
                    int x = i + dx[u], y = j + dy[u];                 // 获取新的位置
                    if (x <= 0 || x > n || y <= 0 || y > m) continue; // 出界判断
                    int a = (i - 1) * m + j, b = (x - 1) * m + y;     // a是指原位置的编号,b是指拓展后位置的编号
                    // int a = i * m + j, b = x * m + y; //并查集的编号其实是很灵活的，不是非得啥号不可.上面的那行代码一样可以AC

                    // join 合并并查集
                    a = find(a), b = find(b);
                    if (a != b) {
                        cnt--;                   // 合并后，连通块的数量将少了一个
                        sz[b] += sz[a];          // a家族成员加入b家族中
                        p[a] = b;                // a认b做父亲
                        area = max(area, sz[b]); // 更新答案
                    }
                }
    // 输出房间总数，输出最大面积
    printf("%d\n%d\n", cnt, area);
    return 0;
}