HDU Black And White(搜索+剪枝）_综合

四色定理是给定的任何一个平面分离成连续的区域，产生一个包含许多区域的图，四种颜色给不同区域涂色，任意相邻的两个区域颜色不能相同。

-维基百科，自由的百科全书

在这个问题上，你必须解决四色问题。嘿，我只是在开玩笑。

你需要解决一个类似的问题：有一个包含从1到K一共K种颜色的N×M棋盘，使得任意两个相邻的区块不能有相同的颜色（如果它们的上、下、左、右任意一边的颜色与自身颜色不同）。第i种颜色可以被使用Ci次。

Input

第一行包含一个整数T（1<=T<= 5000）, T表示测试用例的数量。

对每一个测试用例第一行包含三个整数N,M,K(0<N,M<=5,0<K<=N*M)。

第二行包含K个整数Ci(Ci>0),表示第i种颜色可以被使用的次数。

输入保证C1+ C2+...+ CK=N*M。

Output

对每个测试用例，第一行包含“Case #x:”, x是用例的序号( 从1开始)。

如果有满足条件的涂色方法就输出“YES”，如果没有就输出“NO”。接下来的N行每行由M个表示第i种颜色的数字构成，数字之间有一个空格隔开。

如果有多重涂法，输出其中的一种。

Sample Input

Sample Output

Case #1:
NO
Case #2:
YES
4 3 4
2 1 2
4 3 4
Case #3:
YES
1 2 3
2 3 1
Case #4:
YES
1 2
2 3
3 1

分析：这道题就是搜索，剪枝优化是如果当前未染色的点数为x,(x+1)/2<max(col[i]),就可以return了。这需要作为一个结论记住！

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 8;
int n, m, k, flag, a[maxn][maxn], color[30];
int Next[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
bool vis[maxn][maxn];
bool judge(int x, int y, int col)
{for(int i = 0; i < 4; i++){int nx = x + Next[i][0];int ny = y + Next[i][1];if(nx >= 1 && ny >= 1 && nx <= n && ny <= m && vis[nx][ny]){if(col == a[nx][ny])return false;}}return true;
}
void dfs(int tx, int ty, int cou)
{for(int kk = 1;kk <= k; kk++)if((n*m - cou + 1) / 2 < color[kk])return ;if(cou >= n*m){flag = 0;printf("YES\n");for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(j == m)printf("%d\n", a[i][j]);elseprintf("%d ", a[i][j]);}}return ;}for(int i = 0; i < 4 && flag; i++){int x = tx + Next[i][0];int y = ty + Next[i][1];if(x >= 1 && y >= 1 && x <= n && y <= m && !vis[x][y]){for(int j = 1; j <= k; j++){if(judge(x, y, j) && color[j]){color[j]--;vis[x][y] = true;a[x][y] = j;dfs(x, y, cou + 1);a[x][y] = 0;if(flag == 0)return ;color[j]++;vis[x][y] = false;}}}}if(flag == 0){return ;}
}
int main()
{int T, col[30];scanf("%d", &T);for(int kase = 1; kase <= T; kase++){flag = 1;scanf("%d%d%d", &n, &m, &k);for(int i = 1; i <= k; i++)scanf("%d", &color[i]);printf("Case #%d:\n", kase);for(int i = 1; i <= k; i++){memset(a, 0, sizeof(a));memset(vis, false, sizeof(vis));color[i]--;vis[1][1] = true;a[1][1] = i;dfs(1, 1, 1);color[i]++;if(flag == 0){break;}}if(flag)printf("NO\n");}return 0;
}