题解：P9767 [ROIR 2021 Day 2] 染色

· · 题解

发现数据范围极小，可以直接打表。

#include<bits/stdc++.h>
using namespace std;
int n,m,c;
int a[15][15];
void dfs(int x,int y){
    if(x==n+1){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cout<<a[i][j]<<",";
            }cout<<endl;
        }
        exit(0);
    }
    int nx=x,ny=y+1;if(ny>m)ny=1,nx++;
    int r=rand();
    for(int i=r;i<=c+r;i++){//尝试填颜色 i%c+1
        bool f=1;
        for(int j=1;j<x;j++){
            for(int k=1;k<y;k++){
                if(a[j][k]==a[j][y]&&a[j][y]==a[x][k]&&a[x][k]==i%c+1)f=0;
            }
        }
        if(f){
            a[x][y]=i%c+1;
            dfs(nx,ny);
            a[x][y]=0;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    srand(time(0));
    cin>>n>>m>>c;
    dfs(1,1);
    return 0;
}

其中使用随机数的原因是，这样不会让程序开始尝试填一堆 1，导致后面经常出现无解需要回溯的情况。

输入 8 9 3（输入再大点等待的就不知道多久了），运气好的话，等待几秒，就会出来一份答案：

2,1,1,3,3,3,2,2,2,
3,1,2,3,1,1,1,1,3,
1,3,1,2,2,1,3,2,3,
2,2,1,3,1,2,3,3,1,
1,2,3,2,1,3,2,3,3,
3,2,3,1,3,1,3,2,1,
1,2,2,1,2,3,3,1,2,
1,3,2,2,3,2,1,3,1,

由此可以得到：

int b[15][15]={
    {0},
    {0, 2,1,1,3,3,3,2,2,2,0},
    {0, 3,1,2,3,1,1,1,1,3,0},
    {0, 1,3,1,2,2,1,3,2,3,0},
    {0, 2,2,1,3,1,2,3,3,1,0},
    {0, 1,2,3,2,1,3,2,3,3,0},
    {0, 3,2,3,1,3,1,3,2,1,0},
    {0, 1,2,2,1,2,3,3,1,2,0},
    {0, 1,3,2,2,3,2,1,3,1,0},
    {0, 0,0,0,0,0,0,0,0,0,0},
    {0, 0,0,0,0,0,0,0,0,0,0},
};

再进行小小的填空和手动微调：

int b[15][15]={
    {0},
    {0, 2,1,3,3,1,3,2,1,2,1},
    {0, 2,2,2,1,1,1,1,3,3,3},
    {0, 1,3,2,1,2,3,2,1,1,3},
    {0, 2,3,1,3,3,2,1,1,3,2},
    {0, 2,1,3,2,3,1,3,2,1,3},
    {0, 3,2,1,3,1,2,2,2,1,3},
    {0, 1,2,1,3,2,1,3,3,2,1},
    {0, 1,1,2,2,3,3,1,3,2,2},
    {0, 3,1,1,1,2,3,3,2,3,2},
    {0, 3,3,3,2,2,2,1,3,1,1},
};

再放到原来的代码中：

#include<bits/stdc++.h>
using namespace std;
int n,m,c;
int a[15][15];
int b[15][15]={
    {0},
    {0, 2,1,3,3,1,3,2,1,2,1},
    {0, 2,2,2,1,1,1,1,3,3,3},
    {0, 1,3,2,1,2,3,2,1,1,3},
    {0, 2,3,1,3,3,2,1,1,3,2},
    {0, 2,1,3,2,3,1,3,2,1,3},
    {0, 3,2,1,3,1,2,2,2,1,3},
    {0, 1,2,1,3,2,1,3,3,2,1},
    {0, 1,1,2,2,3,3,1,3,2,2},
    {0, 3,1,1,1,2,3,3,2,3,2},
    {0, 3,3,3,2,2,2,1,3,1,1},
};
void dfs(int x,int y){
    if(x==n+1){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cout<<a[i][j]<<" ";
            }cout<<endl;
        }
        exit(0);
    }
    int nx=x,ny=y+1;if(ny>m)ny=1,nx++;
    for(int i=1;i<=c;i++){//尝试填颜色 i
        bool f=1;
        for(int j=1;j<x;j++){
            for(int k=1;k<y;k++){
                if(a[j][k]==a[j][y]&&a[j][y]==a[x][k]&&a[x][k]==i)f=0;
            }
        }
        if(f){
            a[x][y]=i;
            dfs(nx,ny);
            a[x][y]=0;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>c;
    if(c==2)dfs(1,1);
    else{
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cout<<b[i][j]<<" ";
            }cout<<endl;
        }
    }
    return 0;
}

轻松 AC。