CF1503B 3-Coloring 题解

发布于 2021-04-12  160 次阅读


题意

题目链接

有一张 $n\times\ n$ 的网格,有 $1,2,3$ 三种颜色,每轮交互库会给出一种颜色,你需要在剩余两种颜色中选一种颜色涂在一个格子上,不可以使任何两个相邻格子颜色相同。你需要扮演涂色者将所有格子涂上颜色。

解析

首先我们考虑到,如果有一个空格子,其上下左右四个格子中有两种颜色,你就输了(因为交互库可以一直给出剩余的这种颜色)。因此我们不能让这种情况发生,最好的解决办法就是尽可能只用两种颜色,且不相邻,将第三种颜色当作后手。

以这个思路,我们可以构造出一张理想网格。

我们发现,在 $1$ 或 $2$ 全部被填完之前,不论交互库询问什么,我们都一定能在这个理想网格上填一格(例如,给出 $1$,就在应该填 $2$ 但尚未填的地方填一个 $2$)。

那当我们填完了其中一个数字时呢?我们发现我们已经无敌了,因为剩下的任意一个空格子,其上下左右四个格子都一定只有一种颜色,那么不论交互库给出哪一种颜色,我们都只需要填上另一种颜色,直至整张棋盘都被填满为止。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int c[N][N];
int n,a,T,n1x,n1y,n2x,n2y;
int x,y;
bool fl;
int main(){
    scanf("%d",&n);T=n*n;
    n1x=n1y=1;
    n2x=1,n2y=2;
    x=y=1;
    while(T--){
        scanf("%d",&a);
        if(!fl){//填理想网格
            if(a==1){
                c[n2x][n2y]=2;
                printf("%d %d %d\n",2,n2x,n2y);
                fflush(stdout);
                n2y+=2;
                if(n2y>n){
                    n2x+=1;
                    if(n2x%2==1) n2y=2;
                    else n2y=1;
                }
                if(n2x>n) fl=true;
            }
            else{
                c[n1x][n1y]=1;
                printf("%d %d %d\n",1,n1x,n1y);
                fflush(stdout);
                n1y+=2;
                if(n1y>n){
                    n1x+=1;
                    if(n1x%2==1) n1y=1;
                    else n1y=2;
                }
                if(n1x>n) fl=true;
            }
        }
        else{//有一个数字被填完了
            while(x<=n&&y<=n){
                if(!c[x][y]){
                    if(a==1){
                        if(c[x][y-1]==1||c[x][y+1]==1) c[x][y]=2;
                        else c[x][y]=3;
                    }
                    else if(a==2){
                        if(c[x][y-1]==1||c[x][y+1]==1) c[x][y]=3;
                        else c[x][y]=1;
                    }
                    else{
                        if(c[x][y-1]==1||c[x][y+1]==1) c[x][y]=2;
                        else c[x][y]=1;
                    }
                    printf("%d %d %d\n",c[x][y],x,y);
                    fflush(stdout);
                    y++;if(y>n){y=1;x++;}
                    break;
                }
                y++;if(y>n){y=1;x++;}
            }   
        }
    }
    return 0;
}

月流华 岁遗沙 万古吴钩出玉匣