题解 P4997 【不围棋】

· · 题解

看了一遍题之后，发现其实题意就是模拟游戏进行直到结束，双方的决策你是可以随便定的！

所以，我们只需要轮流找到当前玩家的第一个可以放置棋子的点将其放下，如果找不到就说明游戏结束。

所以，整道题目的解题关键就在于如何高效地支持查询落点是否可行和放置棋子。

首先我们要小小修改一下气的定义。

新的定义是：

一个联通块的气等于她每个棋子四周的空位数量之和。

例如下图（请原谅我使用记事本+画图……），左图中白子联通块的气为3，黑子联通块的气为6， 每个棋子对所在联通块贡献的气为右图所示。

在这个定义中，没有气仍然等价于这块棋会被提走，而这样定义会为后面的操作带来便利。

之后，我们便以下图为例，讲解如何完成这两个操作。

（左图：棋子；右图：该棋子所在联通块的气）

查询落点是否可行

首先，已经放了棋子的位置是显然不能再放棋子的。

如下图，如果我们要在？所在位置放置一个黑子，我们首先把它看作一个单独的棋子（也就是说它现在不与其它黑子相连，也会挡住其它黑子的气），那么它四周的棋子所在的联通块的气要分别-1。再把它自身的气算出。

提示：如果棋子有两个方向上的相邻棋子属于同一个联通块，那么那个联通块的气要-2，因为每个相邻棋子贡献的气都-1了。

然后考虑对方棋子的联通块，如果有一个联通块气为0，就说明这块棋死了，这个落点不可行。图中可见左边白棋气变成了1，而1 > 0，说明不会把她堵死。

最后考虑有没有把自己的棋堵死。这个黑子最终会将它四周的黑棋都连起来，所以只要这个黑子本身或四周任何一块黑棋有气，就能满足要求，反之就不行了。图中虽然上方黑子没气了，但要落下的黑子有两口气，所以不会堵死这个棋子。

这几个条件都满足，说明这个地方是可以放一枚黑棋的。但这里不能放白棋，因为这枚白棋会使上方的黑子没气，而不能把它连起来。

那么

放置棋子

首先先跟上面一样把四周联通块的气-1，然后放上这枚棋子，计算它的气。

然后就是把这枚棋子与四周的同种棋子联通块合并，她们合并后的气即为她们合并前的气之和。

现在这两枚黑棋终于在一个联通块中了。

但是，直接暴力模拟整个过程，复杂度可能高达O(n^6)，只能为你带来30至50分，所以我们要对其进行优化。

并查集优化

看到满篇的“联通块”，再加上她们之间只能合并，不能分开，不难想到用并查集进行优化。把一个联通块看作一个集合，那么就可以在O(\alpha(n))的时间内找到一个棋子所在的联通块，联通块合并只需要把孩子的气加到父亲的气上，也能轻松处理。

现在时间复杂度是O(n^4\alpha(n))：游戏最多有O(n^2)步，每步最多需要判断O(n^2)个位置，每次判断位置是否可行需要O(\alpha(n))，仍然会TLE。

游戏的步数虽然可能可以优化，但不能减少复杂度；判断位置的并查集操作也是O(\alpha(n))不能更少，所以，只能减少每步判断位置的次数。

减少判断次数

（大家不要在意这个难听的标题）

当我们判断出一个位置上不能放黑棋了，那么它有三种情况：

1.现在它会堵死白棋。

2.现在它会堵死黑棋。

3.这里已经有棋子。

白棋也是一样的道理。

也就是说，如果一个位置上检查到不能放一种棋，那么以后也不能放这种棋。所以每个位置对于每种棋只需检查一次。具体地，可以给两个玩家各设一个标记，某个玩家的标记指向她现在需要检查的第一个位置，该标记之前的位置都是她不能放棋子的位置。这样，在整局游戏中，两个标记均只会总共后移至多O(n^2)次。

总复杂度：( 游戏步数O(n^2)+标记后移O(n^2) \times并查集O(\alpha(n)) ) = O(n^2\alpha(n))

这样就可以AC本题了。

Code

F(i) == for(int i=1;i<=n;i++)（枚举一边坐标）

Fc(i) == for(int i=1;i<4;i++)（枚举方向）

Fp(i) == for(Pos i=Pos(1,1);i;++i)（枚举棋盘中的位置）

#include<bits/stdc++.h>
using namespace std;
const int N=666;
int n;
#define F(i) for(int i=1;i<=n;i++)
struct Pos{//表示一个位置，重载了几个运算符
    int x,y;
    Pos(int _x,int _y){
        x=_x,y=_y;
    }
    Pos(){
    }
    Pos operator +(const Pos o)const{
        return Pos(x+o.x,y+o.y);
    }
    bool operator ==(const Pos o)const{
        return x==o.x&&y==o.y;
    }
    bool operator <(const Pos o)const{//只是方便用map
        return make_pair(x,y)<make_pair(o.x,o.y);
    }
    Pos operator ++(){//下一个位置
        y++;
        if(y>n){
            y=1;
            x++;
        }
        return *this;
    }
    operator bool()const{//转化为bool的结果是该位置是否在棋盘内
        return x>=1&&x<=n&&y>=1&&y<=n;
    }
};
#define Fp(i) for(Pos i=Pos(1,1);i;++i)
const Pos d[4]={Pos(1,0),Pos(-1,0),Pos(0,1),Pos(0,-1)};//四个方向
#define Fc(i) for(int i=0;i<4;i++)
template<class T>
struct Board{//资瓷二维数组存取与用Pos直接存取
    T dat[N][N];
    T &operator [](const Pos o){
        return dat[o.x][o.y];
    }
    T *operator [](const int o){
        return dat[o];
    }
};

enum TYPE{//棋盘位置种类
    WALL=-1,BLACK=0,WHITE=1,EMPTY=2
};

Board<Pos> fa;//并查集的父亲数组
Board<int> qi;//联通块的气数记录在根节点的qi上
Board<int> color;//棋盘每个点的种类

void init(){//初始化棋盘
    Fp(p)color[p]=EMPTY;
    Fp(p)qi[p]=0;
    F(i)
        color[i][0]
        =color[i][n+1]
        =color[0][i]
        =color[n+1][i]
        =WALL;
}

Pos find(Pos x){//并查集
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

bool merge(Pos x,Pos y){//并查集
    x=find(x),y=find(y);
    if(x==y)return false;
    qi[y]+=qi[x];
    fa[x]=y;
    return true;
}

bool setgo(Pos p,TYPE c){//在p位置放置颜色为c的棋子
    if(color[p]!=EMPTY)return false;//已经有棋子
    color[p]=c;
    fa[p]=p,qi[p]=0;//新建集合
    Fc(i){
        Pos now=p+d[i];
        if(color[now]==EMPTY){
            qi[p]++;//相邻为空,气+1
        }else if(color[now]!=WALL){
            qi[find(now)]--;//相邻联通块气-1
        }
    }
    Fc(i){
        Pos now=p+d[i];
        if(color[now]==c)merge(p,now);//合并联通块
    }
    return true;
}

bool canset(Pos p,TYPE c){//检查是否能在p位置放置颜色为c的棋子
    if(color[p]!=EMPTY)return false;//只能放在空位
//  printf("Trying (%d,%d) for %d\n",p.x,p.y,c);
    map<Pos,int> eff;//记录如果放了棋子，会给周围的联通块减少的气数
    bool hasqi=false;//己方棋子放下后是否还有气
    Fc(i){
        Pos now=p+d[i];
        if(color[now]==EMPTY){
            hasqi=true;//棋子本身就有气
        }else if(color[now]!=WALL){
            eff[find(now)]++;//该联通块气数将-1
        }
    }
    for(map<Pos,int>::iterator it=eff.begin();it!=eff.end();it++){
        int nowqi=qi[find(it->first)]-it->second;//该联通块剩余气数
//      printf("Eff (%d,%d) [qi=%d]\n",it->first.x,it->first.y,nowqi);
        if(color[it->first]!=c&&nowqi==0)return false;//对方棋子被堵死了
        else if(color[it->first]==c&&nowqi!=0)hasqi=true;//己方棋子有气了
    }
    return hasqi;//己方棋子连起来后是否至少有一口气
}
/*
const char db[]={'X','O','.'}; 
void debug(){
    F(i){
        F(j)printf("%d",qi[find(Pos(i,j))]);
        printf("\n");
    }
    F(i){
        F(j)printf("%c",db[color[i][j]]);
        printf("\n");
    }
    getchar();
}
*/
int main(){
    scanf("%d",&n);
    init();
    Fp(p){
        char ch;
        do{
            ch=getchar();
        }while(ch!='O'&&ch!='X'&&ch!='.');
        //放一开始的棋子
        if(ch=='X')setgo(p,BLACK);
        else if(ch=='O')setgo(p,WHITE);
    }
    TYPE player=BLACK;//黑先
    Pos trying[2];//标记
    trying[BLACK]=Pos(1,1);
    trying[WHITE]=Pos(1,1);
    while(true){
        Pos &nt=trying[player];
        while(nt&&!canset(nt,player))++nt;//从标记向后尝试
        if(!nt){//标记已经在棋盘外了，说明没有合法位置能放了
            printf("%d %d",-1,-1);
            break;//Game Over
        }
        assert(setgo(nt,player));
        printf("%d %d\n",nt.x,nt.y);
//      if(nt.x>4)debug();
        //换玩家
        if(player==BLACK)player=WHITE;
        else player=BLACK;
    }
    return 0;
}

祝大家NOIP.rp++!