题解：AT_arc225_a [ARC225A] Four Coloring

· · 题解

首先看第一个条件：若相邻格子 |X_{i_1,j_1}-X_{i_2,j_2}|=1，则 |Y_{i_1,j_1}-Y_{i_2,j_2}|\ge 2。考虑将原网格的 1 变为 1，2 变为 3，3 变为 1，4 变为 3。但还有一个问题：若相邻格子 |X_{i_1,j_1}-X_{i_2,j_2}|\ge 2，则 |Y_{i_1,j_1}-Y_{i_2,j_2}|\le 1。实际上，这样的一对 X 只有 1 和 3，2 和 4，1 和 4 这三种情况。

我们看一下有哪组数不满足要求：

1 和 4 对应后的 1 和 3 不满足要求，其余全部满足要求。分析一下原因，|Y_{i_1,j_1}-Y_{i_2,j_2}| 只需小于等于 1 即可，要是是 0 就浪费了，所以考虑这样调整：

将原网格的 1 变为 2，2 变为 4。

然后就做完了。贴代码。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define fi first
#define se second
#define gtc getchar
#define ptc putchar
#define pb push_back
#define scnaf scanf
#define prtinf printf
#define pritnf printf
#define retrun return
#define lc p<<1
#define rc p<<1|1
#define yesno(a) a?puts("Yes"):puts("No")
using namespace std;
int n;
int x;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&x);
            if(x==1){
                printf("2 ");
            }
            if(x==2){
                printf("4 ");
            }
            if(x==3){
                printf("1 ");
            }
            if(x==4){
                printf("3 ");
            }
        }
        ptc('\n');
    }
    return 0;
}