题意

给出一个n*m的图，现在有k种颜色让你对这个图每个格子染色，每种颜色最多可以使用col[i]次，问是否存在一种染色方案使得相邻格子的颜色不同。

思路

以为是构造题，结果是爆搜。对于每一个点，如果可以往右边搜，那么就往右边走，如果右边走不了，就往下重新开一行搜。（否则最后可能不是所有格子都染上颜色）

只有一个剪枝：if((rem + 1) / 2 < col[i]) return ; （rem为剩下未染色的格子数），因为如果当前的颜色超过格子数的一半的时候，自己这个颜色必定和自己产生冲突。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

const int N = 1e5 + 11;

int n, m, k, mp[30][30], col[30], flag;

bool check(int x, int y, int id) {

    if(mp[x-1][y] != id && mp[x+1][y] != id && mp[x][y-1] != id && mp[x][y+1] != id) return true;

    return false;

}

void dfs(int x, int y, int rem) {

    if(!rem) { flag = 1; return ; }

    for(int i = 1; i <= k; i++)

        if((rem + 1) / 2 < col[i]) return ;

    for(int i = 1; i <= k; i++) {

        if(!col[i] || !check(x, y, i)) continue;

        col[i]--; mp[x][y] = i;

        if(y < m) dfs(x, y + 1, rem - 1);

        else dfs(x + 1, 1, rem - 1);

        if(flag) return ;

        col[i]++; mp[x][y] = 0;

    }

}

int main() {

    int t; scanf("%d", &t);

    for(int cas = 1; cas <= t; cas++) {

        scanf("%d%d%d", &n, &m, &k);

        for(int i = 1; i <= k; i++) scanf("%d", &col[i]);

        memset(mp, 0, sizeof(mp));

        flag = 0;

        dfs(1, 1, n * m);

        printf("Case #%d:\n", cas);

        if(!flag) puts("NO");

        else {

            puts("YES");

            for(int i = 1; i <= n; i++)

                for(int j = 1; j <= m; j++)

                    printf("%d%c", mp[i][j], j == m ? '\n' : ' ');

        }

//        puts("");

    } return 0;

}

巴特西

HDU 5113：Black And White（DFS）

题意

思路

最新文章

热门文章