补题：J. Robot Factory

传送门：Problem - 1600J - Codeforces

题意：给定一个二维矩阵，每个矩阵中的元素均为 [ 0, 15 ]的范围内，每个矩阵中的元素二进制位上为1时，就代表一堵墙（不能通过），求二维矩阵联通块大小从大到小排列

思路：( dfs )

由于元素是有限的，并且范围很小，于是可以先预处理每个元素的二进制位

在通过 dfs 处理出来每个联通快的大小

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 10;
bool vis[N][N];
int dx[4] = { 0 , 1 , 0 , -1 };
int dy[4] = { -1 , 0 , 1 , 0 }; // 这个要对齐，是 北 东 南 西 ，因为要和元素的二进制对应
int d[16][4];
int cnt; int n, m;
void dfs(vector<vector<int>>& a, int x, int y)
{
    vis[x][y] = true;
    cnt++;
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i]; int yy = y + dy[i];
        if (xx <= 0 || yy <= 0 || xx > n || yy > m || d[a[x][y]][i] || vis[xx][yy])continue;
        dfs(a, xx, yy);
    }
}
void solve()
{
    cin >> n >> m;
    memset(vis, 0, sizeof vis);
    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    priority_queue<int> heap;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!vis[i][j])
            {
                cnt = 0;
                dfs(a, i, j);
                heap.push(cnt);
            }
    while (heap.size())
    {
        cout << heap.top() << " "; heap.pop();
    }
    cout << endl;
}
signed main()
{
    for (int i = 0; i < 16; i++)
        for (int j = 0; j < 4; j++)
            if (i >> j & 1) d[i][j] = 1;
    int tt = 1;
    while (tt--)solve();
    return 0;
}