传送门：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;
}