HDU 5113 – Black And White [DFS+剪枝]

点击打开HDU题目链接

题意

给你一个N×M的矩阵，让你染色，共有K种颜色，每种颜色最多用Ci次，问你怎样染色，如果没有合适的方案输出NO

分析

这个题的正解估计是构造，但是可以搜索做。不过剪枝是很重要的，我们队在做的时候少剪了一个0.5就没有过，真是太坑了…从前往后依次试每个颜色能否放置，当且仅当他左边和上边的颜色跟他不同时可以放置。同时当颜色剩余的最大值大于未涂色/2时要剪枝。

CPP代码

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

const int maxn = 7;
int N, M, K, ok;
int mat[maxn][maxn], cnt[maxn*maxn];

inline bool can(int x, int y, int cur) {
    return cur != mat[x-1][y] && cur != mat[x][y-1];
}

void dfs(int x, int y, int left) {
    if(ok) return;
    if(*max_element(cnt+1, cnt+K+1) > (left+1)/2) return;
    if(!left) { ok = true; return; }
    int xx, yy;
    if(y == M) xx = x + 1, yy = 1;
    else xx = x, yy = y + 1;
    for(int i = 1; i <= K; ++i) {
        if(cnt[i] && can(x, y, i)) {
            --cnt[i];
            mat[x][y] = i;
            dfs(xx, yy, left - 1);
            if(ok) return;
            ++cnt[i];
        }
    }
}

int main() {
    int T, kase = 0; scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d", &N, &M, &K);
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= K; ++i)
            scanf("%d", &cnt[i]);
        memset(mat, 0, sizeof(mat));
        ok = false;
        dfs(1, 1, N * M);
        printf("Case #%d:\n", ++kase);
        if(!ok) puts("NO");
        else {
            puts("YES");
            for(int i = 1; i <= N; ++i)
                for(int j = 1; j <= M; ++j)
                    printf("%d%c", mat[i][j], j==M ? '\n' : ' ');
        }
    }
    return 0;
}