题解（另外一种做法）

前言

这是一篇比 std 难写的做法，思路简单但是实现难搞。

我之前做过类似的题

还有借一下这个地方，求条。

题解

题目意思很简单吧。

看到连通块，可以想到并查集维护每个连通块内的数量，然后再维护每个连通块的气，答案的时候直接输出 find(u) 的答案就可以了。

但是这是二维的，可以用 std::pair 存，但是我考虑到 std 常数巨大，这里用的是 hash 映射成一维的数。

代码：

int change(int x,int y){
	return n*x+y;
} 

然后找四个方向，看是不是相同的子，如果是就合并并查集。

算出并查集，然后就是气怎么解决。

考虑每个点上存有哪些连通块用了这口气，显然是要去重的，因为存的东西小，直接枚举存的。

直接枚举每颗棋子，往四个方向加入这颗子在并查集上的父亲（就是所在连通块）。

最后算的时候直接往父亲加就可以了。

答案就是前文说的，是这个连通块的气的个数，直接 find(u) 的结果。

时间复杂度 $O(n^2)$。

完整代码：

#include <iostream>
#include <vector>
using namespace std;
const int N=1e3+5;
char c[N][N];
int f[N*N+N];
vector<int> a[N*N+N]; 
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int n;
int ans[N*N+N];
int change(int x,int y){
	return n*x+y;
} 
int find(int x){
	return f[x]==x ? x : f[x]=find(f[x]);
}
void merge(int x,int y){
	f[find(y)]=find(x);
}
int main(){
	cin >> n;
	char ch;
	for (int i=1;i<=n;++i){
		c[i][0]='?';
		c[0][i]='?';
		ch=getchar();
		while (ch=='\n' || ch=='\r' || ch==EOF){
			ch=getchar();
		}
		for (int j=1;j<=n;++j){
			c[i][j]=ch;
			ch=getchar();
		}
	}
	int tx,ty,t1,t2;
	for (int i=1;i<=n;++i){
		for (int j=1;j<=n;++j){
			f[change(i,j)]=change(i,j);
//			cout<<change(i,j)<<" ";
		}
//		cout<<endl;
	}
//	cout<<endl;
	for (int i=1;i<=n;++i){//建立并查集 
		for (int j=1;j<=n;++j){
			if (c[i][j]=='.'){
				continue;
			}
			t1=change(i,j);
			for (int k=0;k<4;++k){
				tx=i+dx[k],ty=j+dy[k];
				if (c[tx][ty]!=c[i][j]){
					continue;
				}
				t2=change(tx,ty);
				merge(t1,t2);
			}
		}
	}
//	for (int i=1;i<=n;++i){
//		for (int j=1;j<=n;++j){
//			cout<<f[change(i,j)]<<" ";
//		}
//		cout<<endl;
//	}
//	cout<<endl;
	int t;
	int qwq;
	bool qaq;
	for (int i=1;i<=n;++i){
		for (int j=1;j<=n;++j){
			if (c[i][j]=='.'){
				continue;
			}
			qwq=change(i,j);
			qwq=find(qwq);
			for (int k=0;k<4;++k){
				tx=i+dx[k],ty=j+dy[k];
				if (c[tx][ty]!='.'){//有棋子了 
					continue;
				}
				t=change(tx,ty);
				qaq=true;
				for (const auto &item : a[t]){
					if (item==qwq){ 
						qaq=false;
						break;
					}
				}
				if (qaq){
					a[t].emplace_back(qwq);
					++ans[qwq];
				}
			}
		}
	}
	for (int i=1;i<=n;++i){
		for (int j=1;j<=n;++j){
			if (c[i][j]=='.'){
				printf("0 ");
				continue;
			}
			printf("%d ",ans[find(change(i,j))]);
		}
		putchar('\n');
	}
	return 0;
}

还有借一下这个地方，求条。