题解

比 T4 简单。

简单的并查集板子题，参考 01迷宫_信奥算法普及/提高--ACGO题库。不做详细解释。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int a[1005][1005];
int father[1000005], size[1000005];
bool vis[1000005];
vector <int> v;
int n, m;
int find(int n){return (father[n] == n ? n : father[n] = find(father[n]));}//查找父亲节点
void merge(int x, int y){//合并
	int n = find(x), m = find(y);
	if(n == m) return;//如果不判断是否在同一集合会使size的值重复加
	father[min(n, m)] = max(n, m);
	size[max(n, m)] += size[min(n, m)];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
			father[(i - 1) * m + j] = (i - 1) * m + j;//初始化
			size[(i - 1) * m + j] = 1;
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(i > 1 && (~a[i][j] & 8) && (~a[i - 1][j] & 2)){//如果这格的北方无墙且上一格的南方无墙就说明可以到达
				merge((i - 1) * m + j, (i - 2) * m + j);//和上方合并
			}
			if(j > 1 && (~a[i][j] & 1) && (~a[i][j - 1] & 4)){//如果这格的西方无墙且左一格的东方无墙就说明可以到达
				merge((i - 1) * m + j, (i - 1) * m + j - 1);//和左方合并
			}
		}
	}
	for(int i = 1; i <= n * m; i++){
		if(!vis[find(i)]){
			vis[find(i)] = 1;
			v.push_back(size[find(i)]);//记录大小
		}
	}
	sort(v.begin(), v.end(), greater <int>());//从大到小排序
	for(int i:v) cout << i << ' ';
	

	return 0;
}

时间复杂度：$O(N\times M\log (N\times M))$。