1636 < ICPC Prelim < Challenges | Aizu Online Judge
問題
立方体が $n \times n$ の正方形状に並んだ板が $6$ つ与えられる。
これらは外周が一部欠けているもある。
これら $6$ つの板を組み合わせて、 $n \times n \times n$ の立方体の表面を作れるか判定せよ。なお各板はどちらの面を表面にしてもよい(つまり反転できる)ものとする。
制約
- $3 \leq n \leq 9$
- $n$ は奇数
考察
枝刈り DFS でシミュレーションするだけ(ちなみに DFS ではなく各板の配置・向きを全探索すると TLE する)。
ただ実装がかなり面倒くさい。以下では実際に $n \times n \times n$ の配列を塗っていくのだが、どの面に置くかによって 3 つの場合分け(といってもほとんどコピペだが)が生じている。
実装例
Run #4814241 < misteer < Solutions | Aizu Online Judge
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using Face = std::vector<std::string>;
using Cube = std::vector<Face>;
int n;
std::vector<Face> faces(6);
Cube cube;
void flip(Face& face) {
for (auto& s : face) std::reverse(s.begin(), s.end());
}
void rotate(Face& face) {
flip(face);
for (int x = 0; x < n; ++x) {
for (int y = 0; y < x; ++y) {
std::swap(face[x][y], face[y][x]);
}
}
}
bool dfs(int b) {
int d = __builtin_popcount(b);
if (d == 6) return true;
int z = (d % 2 == 0 ? 0 : n - 1);
for (int i = 0; i < 6; ++i) {
if ((b >> i) & 1) continue;
auto& face = faces[i];
for (int p = 0; p < 2; ++p) {
// flip
flip(face);
for (int q = 0; q < 4; ++q) {
// rotate
rotate(face);
if (d < 2) {
bool ok = true;
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
if (face[x][y] == 'X' &&
cube[x][y][z] == 'X') ok = false;
}
}
if (!ok) continue;
// paint
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
if (face[x][y] == 'X') cube[x][y][z] = 'X';
}
}
if (dfs(b | (1 << i))) return true;
// recover
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
if (face[x][y] == 'X') cube[x][y][z] = '.';
}
}
} else if (d < 4) {
bool ok = true;
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
if (face[x][y] == 'X' &&
cube[x][z][y] == 'X') ok = false;
}
}
if (!ok) continue;
// paint
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
if (face[x][y] == 'X') cube[x][z][y] = 'X';
}
}
if (dfs(b | (1 << i))) return true;
// recover
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
if (face[x][y] == 'X') cube[x][z][y] = '.';
}
}
} else {
bool ok = true;
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
if (face[x][y] == 'X' &&
cube[z][x][y] == 'X') ok = false;
}
}
if (!ok) continue;
// paint
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
if (face[x][y] == 'X') cube[z][x][y] = 'X';
}
}
if (dfs(b | (1 << i))) return true;
// recover
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
if (face[x][y] == 'X') cube[z][x][y] = '.';
}
}
}
}
}
}
return false;
}
bool solve() {
std::cin >> n;
if (n == 0) return false;
int cnt = 0;
for (auto& face : faces) {
face.resize(n);
for (auto& s : face) {
std::cin >> s;
cnt += std::count(s.begin(), s.end(), 'X');
}
}
if (cnt != n * n * n - (n - 2) * (n - 2) * (n - 2)) {
std::cout << "No\n";
return true;
}
cube.resize(n);
for (auto& face : cube) {
face.resize(n);
for (auto& s : face) s.assign(n, '.');
}
std::cout << (dfs(0) ? "Yes" : "No") << "\n";
return true;
}
|