题目意思很好懂,给你一个矩阵,然后给你刚好矩阵这么大小的颜色,颜色有很多种,加起来肯定等于矩阵大小。问能否放置颜色使得相邻颜色之间没有相同的颜色。

明显的dfs题,但是直接dfs铁定超时,所以就得剪枝,比赛的时候想到了剪一半数量,但是觉得不够就没试,然后发现剪一半能过。。。

剪一半,每次dfs之前循环一遍所有颜色数目,剩下的格子数量除以2向上取整数,每个颜色都得小于这个数,不然肯定会有相邻相同的颜色。

(dfs写的比较垃圾,时间比较长)

代码:

StatusAccepted
Time889ms
Memory1736kB
Length1240
LangC++
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=30;
int mat[maxn][maxn], clr[maxn];
int t, n, m, num;
bool dfs(int x, int y){
    int ls=n*m-(x-1)*m+y-1;
    for(int i=1;i<=num;i++){
        if(clr[i]>(ls+1)/2)return 0;
    }
    for(int i=1;i<=num;i++){
        if(clr[i]&&mat[x][y-1]!=i&&mat[x-1][y]!=i){
            clr[i]--;
            mat[x][y]=i;
            if(x==n&&y==m)return 1;
            int nx=x, ny=x;
            if(y==m){nx=x+1;ny=1;}
            else{nx=x;ny=y+1;}
            if(!dfs(nx, ny))
                clr[i]++;
            else return 1;
        }
    }
    return 0;
}
int main()
{
    scanf("%d", &t);
    for(int cas=1;cas<=t;cas++){
        scanf("%d%d%d", &n, &m, &num);
        for(int i=1;i<=num;i++){
            scanf("%d", &clr[i]);
        }
        printf("Case #%d:\n", cas);
        memset(mat, -1, sizeof(mat));
        if(dfs(1, 1)){
            printf("YES\n");
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++){
                    printf("%d", mat[i][j]);
                    printf("%s", j==m?"\n":" ");
                }
            }
        }
        else{
            printf("NO\n");
        }
    }
    return 0;
}