HDU - 5113 Black And White 搜索+剪枝 （ 2014ACM/ICPC亚洲区北京站-重现赛（感谢北师和上交））

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctype.h>
#include <vector>
#include <algorithm>
#include <sstream>
#define PI acos(-1.0)
#define in freopen("in.txt", "r", stdin)
#define out freopen("out.txt", "w", stdout)
using namespace std;
typedef long long ll;
const int maxn =
7, INF = 0x3f3f3f3f, mod = 1e9 + 7;
int T, n, m, k;
int mp[maxn][maxn];
int a[maxn*maxn], vis[maxn][maxn];
int dx[5] = {1, 0, -1, 0};
int dy[5] = {0, 1, 0, -1};
void init() {
scanf("%d %d %d", &n, &m, &k);
for(int i = 1; i <= k; ++i)
scanf("%d", &a[i]);
memset(mp, 0, sizeof mp);
}
bool dfs(int x, int y, int cnt) {
if(cnt == n*m) return true;
for(int ii = 0; ii < 4; ++ii) {
int xx = x + dx[ii], yy = y + dy[ii];
if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
if(vis[xx][yy]) continue;
vis[xx][yy] = 1;
int f = 0;
for(int i = 1; i <= k; ++i) {
if(a[i]) {
int j;
for(j = 0; j < 4; ++j) {
int nx = xx + dx[j], ny = yy + dy[j];
if(mp[nx][ny] == i) break;
}
if(j == 4) {
f = 1;
a[i]--;
mp[xx][yy] = i;
int t = (n*m-cnt)/2, f_ = 1;
for(int i = 1; i <= k; ++i)
if(a[i] > t) { f_ = 0; break; }
if(f_ && dfs(xx, yy, cnt+1)) return true;
a[i]++;
mp[xx][yy] = 0;
}
}
}
if(f == 0) { vis[xx][yy] = 0; return false; }
vis[xx][yy] = 0;
}
return false;
}
void solve() {
for(int i = 1; i <= k; ++i) {
a[i]--;
memset(vis, 0, sizeof vis);
vis[1][1] = 1;
mp[1][1] = i;
if(dfs(1, 1, 1)) {
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' : ' '));
}
//cout << "++++++++++++++++++++++++2333" << endl;
return;
}
a[i]++;
vis[1][1] = 0;
mp[1][1] = 0;
}
puts("NO");
}
int main() {
scanf("%d", &T);
int kase = 1;
while(T--) {
init();
printf("Case #%d:n", kase++);
solve();
}
return 0;
}