并查集题解

实际上思路并不难 具体过程如下：
1.用并查集合并成一个个连通块
2.计算出每个连通块的气数（用set记录每个相邻空白的坐标就行，比vector暴力更快，时间复杂度为 $O(\log n)$，而且实现简单）
ok开始实现

#include <iostream>
#include <cstdio>
#include <set> 
#define get(x, y) ((x - 1) * n + y)//将坐标转换成数值
using namespace std;
int n;
char mp[1005][1005];
int dir[4][2] = {-1, 0, 0, -1, 0, 1, 1, 0};
int father[1000005];//并查集
set <int> s[1000005];
int find(int n){
	if(father[n] != n) father[n] = find(father[n]);
	return father[n];
}
void merge(int x, int y){
	father[find(x)] = find(y);
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++){
    	scanf("%s", mp[i] + 1);
    }
	for(int i = 1; i <= n * n; i++){
		father[i] = i;//初始化
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(mp[i][j] == '.') continue;
			int tmp = get(i, j);
			for(int k = 0; k < 4; k++){
				int xx = i + dir[k][0], yy = j + dir[k][1];
				if(mp[xx][yy] == mp[i][j]) merge(tmp, get(xx, yy));//如果周围有相同色的就合并
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(mp[i][j] == '.') continue;
			int tmp = find(get(i, j));
			for(int k = 0; k < 4; k++){
				int xx = i + dir[k][0], yy = j + dir[k][1];
				if(mp[xx][yy] == '.') s[tmp].insert(get(xx, yy));//如果是空点将该气加入set中
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cout << s[find(get(i, j))].size() << ' ';//算出总气数
		}cout << endl;
	}

    return 0;
}