1985H1 Maximize the Largest Component (Easy Version)

Maximize the Largest Component (Easy Version)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+5;
int pre[N];
int siz[N];
int row[N],col[N];
int vis[N];
int n,m;

int root(int x){
	return pre[x]=(pre[x]==x)?x:root(pre[x]);
}

int cal(int x,int y){
	return x*m+y;
}

void merge(int x,int y){
	int fx=root(x);
	int fy=root(y);
	if(fx!=fy){
		siz[fx]+=siz[fy];
		pre[fy]=fx;
	}
}

void init(){
	for(int i=0;i<=n*m;i++){
		row[i]=col[i]=0;
		pre[i]=i;
		siz[i]=1;
		vis[i]=0;
	}
}

void solve(){
	cin>>n>>m;
	init();
	vector<string>s(n);
	for(int i=0;i<n;i++)cin>>s[i];

	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(s[i][j]!='#')continue;
			row[i]++;
			col[j]++;
			//初始化，记录每行每列"."的个数
			int cur=cal(i,j);
			if(i!=0&&s[i-1][j]=='#')merge(cur,cal(i-1,j));//如果"."相邻为"#"合并
			if(j!=0&&s[i][j-1]=='#')merge(cur,cal(i,j-1));
		}
	}

	int ans=0;
	
	for(int i=0;i<n;i++){
		int cur=m-row[i];//减去这行所有的"."
		for(int j=0;j<m;j++){
			if(i!=0&&s[i-1][j]=='#'&&!vis[root(cal(i-1,j))]){
				vis[root(cal(i-1,j))]=1;
				cur+=siz[root(cal(i-1,j))];
			}
			if(i!=n-1&&s[i+1][j]=='#'&&!vis[root(cal(i+1,j))]){
				vis[root(cal(i+1,j))]=1;
				cur+=siz[root(cal(i+1,j))];
			}
			if(s[i][j]=='#'&&!vis[root(cal(i,j))]){
				vis[root(cal(i,j))]=1;
				cur+=siz[root(cal(i,j))];
			}
		}
		//还原vis
		for(int j=0;j<m;j++){
			if(i!=0)vis[root(cal(i-1,j))]=0;
			if(i!=n-1)vis[root(cal(i+1,j))]=0;
			vis[root(cal(i,j))]=0;
		}
		ans=max(ans,cur);
	}

	for(int i=0;i<m;i++){//相同
		int cur=n-col[i];
		for(int j=0;j<n;j++){
			if(i!=0&&s[j][i-1]=='#'&&!vis[root(cal(j,i-1))]){
				vis[root(cal(j,i-1))]=1;
				cur+=siz[root(cal(j,i-1))];
			}
			if(i!=m-1&&s[j][i+1]=='#'&&!vis[root(cal(j,i+1))]){
				vis[root(cal(j,i+1))]=1;
				cur+=siz[root(cal(j,i+1))];
			}
			if(s[j][i]=='#'&&!vis[root(cal(j,i))]){
				vis[root(cal(j,i))]=1;
				cur+=siz[root(cal(j,i))];
			}
		}
		//还原
		for(int j=0;j<n;j++){
			if(i!=0)vis[root(cal(j,i-1))]=0;
			if(i!=m-1)vis[root(cal(j,i+1))]=0;
			vis[root(cal(j,i))]=0;
		}
		ans=max(ans,cur);
	}

	cout<<ans<<"\n";

}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;cin>>t;
	while(t--){
		solve();
	}

	return 0;
}