Description:

In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color.
— Wikipedia, the free encyclopedia

In this problem, you have to solve the 4-color problem. Hey, I’m just joking.

You are asked to solve a similar problem:

Color an N × M chessboard with K colors numbered from 1 to K such that no two adjacent cells have the same color (two cells are adjacent if they share an edge). The i-th color should be used in exactly ci cells.

Matt hopes you can tell him a possible coloring.

Input:

The first line contains only one integer T (1 ≤ T ≤ 5000), which indicates the number of test cases.

For each test case, the first line contains three integers: N, M, K (0 < N, M ≤ 5, 0 < K ≤ N × M ).

The second line contains K integers ci (ci > 0), denoting the number of cells where the i-th color should be used.

It’s guaranteed that c1 + c2 + · · · + cK = N × M .

Output:

For each test case, the first line contains “Case #x:”, where x is the case number (starting from 1).

In the second line, output “NO” if there is no coloring satisfying the requirements. Otherwise, output “YES” in one line. Each of the following N lines contains M numbers seperated by single whitespace, denoting the color of the cells.

If there are multiple solutions, output any of them.

Sample Input:

4
1 5 2
4 1
3 3 4
1 2 2 4
2 3 3
2 2 2
3 2 3
2 2 2

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

题目链接

用k种颜色(每种颜色有c[i]个)为n*m的地图进行涂色,使共同边界方格具有不同的颜色。

dfs(深度优先搜索)枚举所有情况搜索解,这里在搜索的时候有一个很重要的剪枝(看代码)。

此题行末无空格!!

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define XDebug(x) cout<<#x<<"="<<x<<endl;
#define ArrayDebug(x,i) cout<<#x<<"["<<i<<"]="<<x[i]<<endl;
#define print(x) out(x);putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int INF = 0x3f3f3f3f;
const int maxn = 1e2 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
template <class T>
inline bool read(T &ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) {
        return 0;
    }
    while (c != '-' && (c < '0' || c > '9')) {
        c = getchar();
    }
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') {
        ret = ret * 10 + (c - '0');
    }
    ret *= sgn;
    return 1;
}
template <class T>
inline void out(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) {
        out(x / 10);
    }
    putchar(x % 10 + '0');
}

int T;
int N, M, K;
bool finish;
int num[maxn << 1];
int plat[maxn][maxn];

bool check(int x, int y, int color) {
	if (x > 0 && plat[x - 1][y] == color) {
		return 0;
	}
	if (y > 0 && plat[x][y - 1] == color) {
		return 0;
	}
	return 1;
}

void dfs(int x, int y) {
	// 若剩下的点的二分之一小于任一颜色的数量(一定有两个相邻的方格被染成同一种颜色),剪枝
	for (int i = 1; i <= K; ++i) {
		int cnt = (N - x - 1) * M + (M - y);
		if ((cnt + 1) / 2 < num[i]) {
			return;
		}
	}
	for (int i = 1; i <= K; ++i) {
		if (num[i]) {
			if (check(x, y, i)) {
				plat[x][y] = i;
				if (x == N - 1 && y == M - 1) {
					finish = 1;
					return;
				}
				num[i]--;
				dfs(y == M - 1 ? x + 1 : x, y == M - 1 ? 0 : y + 1);
				if (finish) {
					return;
				}
				num[i]++;
			}
		}
	}
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	read(T);
	for (int Case = 1; Case <= T; ++Case) {
		read(N); read(M); read(K);
		for (int i = 1; i <= K; ++i) {
			read(num[i]);
		}
		mem(plat, 0);
		finish = 0;
		dfs(0, 0);
		printf("Case #%d:\n", Case);
		if (finish) {
			printf("YES\n");
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < M; ++j) {
					printf("%d", plat[i][j]);
					// 此题行末无空格!!!
					if (j != M - 1) {
						printf(" ");
					}
				}
				printf("\n");
			}
		}
		else {
			printf("NO\n");
		}
	}
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("gedit out.txt");
#endif
    return 0;
}