[ICPC2020 Nanjing R] Go

· · 题解

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

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

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

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

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

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

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

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

时间复杂度 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;
}