HDU 5113 DFS+枝切り

HDU 5113タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=5113 題意:マトリクス、いくつかの色、および各色の使用回数を与えます.色を塗った後、隣接する格子の色が異なるようにする合法的な案を聞いた.合法的なシナリオがimpossibleを出力していません.構想:カード定数、構造でTを体得する.枝を切って、1つの色の個数が残りの格子の個数の半分より大きいと減らします.自分で书くときは毎回色を余剰数でソートしていますが…実はそのまま前から后まで探しておけばいいのですが、ソート会Tとか…ソース:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
const int MAXN = 5 + 1;
int gra[MAXN][MAXN];
int cnt[MAXN*MAXN];
int n, m, l;
bool valid(int x, int y)
{
    if(x > 1 && gra[x][y] == gra[x - 1][y]) return false;
    if(y > 1 && gra[x][y] == gra[x][y - 1]) return false;
    return true;
}
bool dfs(int x, int y, int mark, int rest)
{
    gra[x][y] = mark;
    if(!valid(x, y))    return false;
    for(int i = 1 ; i <= l ; i++)
        if(cnt[i] > (rest + 1) / 2) return false;
    cnt[mark]--;
    if(x == n && y == m)    return true;
    int ty = y == m ? 1 : y + 1;
    int tx = y == m ? x + 1 : x;
    for(int i = 1 ; i <= l ; i++){
        if(cnt[i] != 0 && dfs(tx, ty, i, rest - 1)){
            return true;
        }
    }
    cnt[mark]++;
    return false;
}
int main()
{
    int t;
    scanf("%d", &t);
    for(int cas = 1 ; cas <= t ; cas++){
        scanf("%d%d%d", &n, &m, &l);
        for(int i = 1 ; i <= l ; i++)
            scanf("%d", &cnt[i]);
        int ok = 0;
        for(int i = 1 ; i <= l ; i++){
            if(dfs(1, 1, i, n * m)){
                ok = 1;
                break;
            }
        }
        printf("Case #%d:
", cas);
        if(ok){
            printf("YES
");
            for(int i = 1 ; i <= n ; i++){
                int f = 1;
                for(int j = 1 ; j <= m ; j++){
                    if(f)   f = 0;
                    else    printf(" ");
                    printf("%d", gra[i][j]);
                }
                printf("
");
            }
        }
        else    printf("NO
");
    }
    return 0;
}