首先是改变气的定义，使得容易计算，这个很好理解。

然后使用并查集，因为要维护整个连通块的性质。

最后的难点在于，落子把同颜色的连通块连接了，但假如本身就是同一个连通块则不应该计数，所以其实连通块的气不应该手动维护，而应该全权交给并查集去处理。

当然去重之后也是对的。

#include
    
     using namespace std;typedef unsigned long long ull;const int INF=0x3f3f3f3f;int solve();int main() {#ifdef Yinku    freopen("Yinku.in","r",stdin);#endif // Yinku    solve();}int n;char g[605][605];inline int id(int i,int j) {    return (i-1)*n+j;}inline void aid(int f,int &i,int &j) {    j=f%n;    if(j==0)        j=n;    i=(f-j)/n+1;    return;}int fa[360005];//并查集int qi[360005];//id对应的位置的气，只有并查集的根保存正确的气queue
     
       Q[2];int dx[4]= {-1,1,0,0};int dy[4]= {0,0,-1,1};char col[2]= {'X','O'};int find(int x) {    int r=x;    while(fa[r]!=r) {        r=fa[r];    }    while(x!=r) {        int k=fa[x];        fa[x]=r;        x=k;    }    return r;}void merge(int x,int y) {    x=find(x);    y=find(y);    if(x==y)        return;    fa[y]=x;    return;}void Exit() {    puts("-1 -1");    exit(0);}inline void Show() {    cout<<"G:"<
      
       =1&&x<=n&&y>=1&&y<=n&&g[x][y]==col[ot])            if(qi[find(id(x,y))]<=0){                need=1;                break;            }    }    if(!need)        return 0;    for(int k=0; k<4; k++) {        int x=ox+dx[k];        int y=oy+dy[k];        if(x>=1&&x<=n&&y>=1&&y<=n&&g[x][y]!='.')            qi[find(id(x,y))]++;    }    return 1;}bool RollBackThisColor(int ox,int oy,int th,int ot,int Qi) {    int newQi=Qi;    vector
       
         visited;    for(int k=0; k<4; k++) {        int x=ox+dx[k];        int y=oy+dy[k];        /*这样同一个连通块的气被重复计算了        if(x>=1&&x<=n&&y>=1&&y<=n&&g[x][y]==col[th])            newQi+=qi[find(id(x,y))];        */        if(x>=1&&x<=n&&y>=1&&y<=n&&g[x][y]==col[th]){            int r=find(id(x,y));            int s=visited.size();            bool Visited=0;            for(int i=0;i
        
         =1&&x<=n&&y>=1&&y<=n&&g[x][y]!='.')            qi[find(id(x,y))]++;    }    return 1;}int Move(int th,int ot) {    while(1) {        //Show();        //交替下        while(1) {            //重复下同一种棋，防爆栈            if(Q[th].empty()) {                Exit();            }            int f=Q[th].front();            Q[th].pop();            int x,y;            aid(f,x,y);            //cout<<"color="<
         
          <<" ("<
          
           <<","<
           
            <<")"<
            
             =1&&xx<=n&&yy>=1&&yy<=n) { if(g[xx][yy]!='.') qi[find(id(xx,yy))]--; else Qi++; } } //Show(); if(RollBackOtherColor(x,y,th,ot)) { //把另一种颜色提子了，回滚重来 //cout<<"RollBack by other color"<
             
              =1&&x<=n&&y>=1&&y<=n&&g[x][y]!='.') qi[find(id(x,y))]++; } } } return ;}int solve() { scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%s",g[i]+1); } Init(); Move(0,1); //先下黑棋 return 0;}