P16166 [ICPC 2015 NAIPC] Magic Checkerboard

ooliver 发布于 1 小时前 8 次阅读 OI

AI 摘要

棋盘填数难题：如何用奇偶性破局？当只有一行一列时，贪心即可；但二维棋盘暗藏玄机——按对角线染色后，黑白格子奇偶竟能互相推导！只需知道两个格子的奇偶性，就能推演出整个填数方案。想知道这个神奇的染色法如何破解复杂棋盘吗？

P16166 [ICPC 2015 NAIPC] Magic Checkerboard

特殊情况：$n=1$ 或 $m=1$

这个很好想，应为在这种情况下不存在两个格子只有一个公共角，所以只需要贪心地满足横向或者纵向是递增的就可以了，期间加上对已经放了数的格子的判断。

一般情况：$n\neq1$ 且 $m\neq1$

我们可以把表格按对角线染成黑白两种颜色，如下图：

黑白格子里只要知道其中一个格子的奇偶，就能推出其他同颜色的格子的奇偶。并且在图中，格子内圆圈颜色相同的一定同奇偶。注意这是建立在表格是二维的情况下的推论，所以我们需要特判一维的情况。

知道这点就很好写了，我们用两个布尔类型的变量存储 $(1,1)$ 与 $(1,2)$ 两个格子的奇偶性，就可以推出整个表格的奇偶性，最后贪心填数即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=2e3+5;
int n,m;
int a[N][N],b[N][N];

int solve(int tag1,int tag2){
    int ans=0;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
        b[i][j]=a[i][j];
        int x=max(b[i-1][j],b[i][j-1])+1,y;
        if(i%2==1&&j%2==1) y=tag1;
        if(i%2==0&&j%2==0) y=!tag1;
        if(i%2==1&&j%2==0) y=tag2;
        if(i%2==0&&j%2==1) y=!tag2;
        if(x%2!=y) x++;
        if(b[i][j]){
            if(x<=b[i][j]) ans+=b[i][j];
            else return 1e18;
        }
        else ans+=(b[i][j]=x);
    }
    return ans;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int ans=1e18,tag1=-1,tag2=-1;
    cin>>n>>m;
    if(n==1||m==1){//特判一维的情况
        ans=0;
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(!a[i][j]) a[i][j]=max(a[i-1][j],a[i][j-1])+1;
            else if(a[i][j]<max(a[i-1][j],a[i][j-1])+1){cout<<-1;return 0;}
            ans+=a[i][j];
        }
        cout<<ans;
        return 0;
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
        cin>>a[i][j];
        if(!a[i][j]) continue;
        if(i%2==1&&j%2==1){
            if(tag1==-1) tag1=a[i][j]%2;
            else if(tag1!=a[i][j]%2){cout<<-1;return 0;}
        }
        if(i%2==0&&j%2==0){
            if(tag1==-1) tag1=(a[i][j]+1)%2;
            else if(tag1!=(a[i][j]+1)%2){cout<<-1;return 0;}
        }
        if(i%2==1&&j%2==0){
            if(tag2==-1) tag2=a[i][j]%2;
            else if(tag2!=a[i][j]%2){cout<<-1;return 0;}
        }
        if(i%2==0&&j%2==1){
            if(tag2==-1) tag2=(a[i][j]+1)%2;
            else if(tag2!=(a[i][j]+1)%2){cout<<-1;return 0;}
        }
    }
    //如果所有黑格子或所有白格子都不确定，那就枚举
    if(tag1==-1&&tag2==-1){
        ans=min(ans,solve(1,1));
        ans=min(ans,solve(1,0));
        ans=min(ans,solve(0,1));
        ans=min(ans,solve(0,0));
    }
    else if(tag1!=-1&&tag2==-1){
        ans=min(ans,solve(tag1,1));
        ans=min(ans,solve(tag1,0));
    }
    else if(tag1==-1&&tag2!=-1){
        ans=min(ans,solve(1,tag2));
        ans=min(ans,solve(0,tag2));
    }
    else ans=min(ans,solve(tag1,tag2));
    cout<<(ans==1e18?-1:ans);
    return 0;
}