自动搬运

查看原文

来自洛谷，原作者为

	C1942huangjiaxu 我将终究顺流入大海

搬运于2025-08-24 22:50:14，当前版本为作者最后更新于2024-03-27 19:27:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

将白棋看成点，相邻的白棋之间连一条边。

如果一个棋子的周围有空位，则认为这个棋子是活棋子。

如果一个连通块中有活棋子，那么这个连通块就是活的。

答案即为死的连通块大小和，需要维护每个连通块的大小和活棋子数。

求出初始局面的答案，考虑改变一枚棋子的颜色，可能改变的只有与它相邻的连通块。

我们先把这些连通块的答案减去，改变颜色后，再把新的答案加上。

如果黑棋变为白棋，直接把相邻连通块信息合并即可，一个连通块可能有多条边与该棋子相连，注意去重。

如果白棋变为黑棋，用 tarjan 求出割点，并建立 DFS 树，分 $2$ 种情况讨论。

• 如果不是割点，那么没有产生新的连通块，只需要判断该棋子是否是原先连通块唯一的活棋子即可。

• 如果是割点，会分裂出多个连通块，枚举 DFS 树中儿子分裂出去的连通块，用整个连通块的信息减去儿子分裂出去的连通块的信息，即可得到父亲所在连通块的信息。

时间复杂度 $O(n^2)$，主要难点在代码实现上。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=1e6+5,B=1e6+7,P=1e9+7;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int T,n,id[N][N],cnt,px[M],py[M],ans,va[M],Ans;
int dfn[M],low[M],co[M],tot,cl[M],Cl[M],sz[M],Sz[M];
bool ch[M],cut[M];
vector<int>e[M],g[M];
char s[N][N];
bool onb(int x,int y){
	return x>0&&x<=n&&y>0&&y<=n;
}
bool lf(int x,int y){
	for(int k=0;k<4;++k){
		int i=x+dx[k],j=y+dy[k];
		if(onb(i,j)&&s[i][j]=='.')return true;
	}
	return false;
}
void tarjan(int x){
	dfn[x]=low[x]=++dfn[0],co[x]=tot,cl[x]=ch[x],sz[x]=1;
	for(auto v:e[x]){
		if(!dfn[v]){
			g[x].push_back(v);
			tarjan(v);
			low[x]=min(low[x],low[v]);
			if(low[v]>=dfn[x])cut[x]=true;
			cl[x]+=cl[v],sz[x]+=sz[v];
		}else low[x]=min(low[x],dfn[v]);
	}
}
void calc(int x){
	if(!Cl[co[x]])va[x]-=Sz[co[x]];
	if(cut[x]){
		int Rs=Sz[co[x]]-1,Rc=Cl[co[x]]-ch[x];
		for(auto v:g[x])if(low[v]>=dfn[x]){
			if(!cl[v])va[x]+=sz[v];
			Rs-=sz[v],Rc-=cl[v];
		}
		if(!Rc)va[x]+=Rs;
	}else{
		if(Cl[co[x]]-ch[x]==0)va[x]+=Sz[co[x]]-1;
	}
	for(auto v:g[x])calc(v);
}
int rev(int i,int j){
	if(s[i][j]=='o')return va[id[i][j]];
	int res=0,Rs=1,Rc=lf(i,j);
	set<int>S;
	for(int k=0;k<4;++k){
		int x=i+dx[k],y=j+dy[k];
		if(onb(x,y)&&s[x][y]=='o')S.insert(co[id[x][y]]);
	}
	for(auto v:S){
		if(!Cl[v])res-=Sz[v];
		Rs+=Sz[v],Rc+=Cl[v];
	}
	if(!Rc)res+=Rs;
	return res;
}
void solve(){
	scanf("%d",&n);
	for(int i=1;i<=cnt;++i)e[i].clear(),g[i].clear(),co[i]=va[i]=dfn[i]=0;
	cnt=dfn[0]=tot=ans=Ans=0;
	for(int i=1;i<=n;++i)scanf("%s",s[i]+1);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)if(s[i][j]=='o'){
			id[i][j]=++cnt;
			ch[cnt]=lf(i,j);
			px[cnt]=i,py[cnt]=j;
		}
	for(int i=1;i<=cnt;++i)
		for(int j=0;j<4;++j){
			int x=px[i]+dx[j],y=py[i]+dy[j];
			if(onb(x,y)&&s[x][y]=='o')e[i].push_back(id[x][y]);
		}
	for(int i=1;i<=cnt;++i)if(!co[i]){
		++tot;
		tarjan(i);
		Cl[tot]=cl[i],Sz[tot]=sz[i];
		if(g[i].size()>1)cut[i]=true;
		else cut[i]=false;
		if(!cl[i])ans+=Sz[tot];
		calc(i);
	}
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(s[i][j]!='.'){
		int t=ans+rev(i,j);
		Ans=(1ll*Ans*B+t)%P;
	}
	printf("%d\n",Ans);
}
int main(){
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}