poj 1052 Plato's Blocks
共 1445字，需浏览 3分钟
· 2021-12-13
Plato's Blocks
Description
Plato believed what we perceive is but a shadow of reality. Recent archaeological excavations have uncovered evidence that this belief may have been encouraged by Plato's youthful amusement with cleverly-designed blocks. The blocks have the curious property that, when held with any face toward a light source, they cast shadows of various letters, numbers, shapes, and patterns. It is possible for three faces incident to a corner to correspond to three different shadow patterns. Opposite faces, of course, cast shadows which are mirror images of one another.
The blocks are formed by gluing together small cubes to form a single, connected object. As an example, the figures below show, layer by layer, the internal structure of a block which can cast shadows of the letters "E", "G", or "B".
Only a partial set of blocks was discovered, but the curious scientists would like to determine what combinations of shadows are possible. Your program, the solution to this problem, will help them! The program will input groups of shadow patterns, and for each group will report whether or not a solid can be constructed that will cast those three shadows.
Input
The input contains a sequence of data sets, each specifying a dimension and three shadow patterns. The first line of a data set contains a positive integer 1 <= n <= 20 that specifies the dimensions of the input patterns. The remainder of the data set consists of 3n lines, each containing a string of n "X" and "-" characters. Each group of n lines represents a pattern. Where an "X" appears a shadow should be cast by the final solid, and where a "-" appears, light should pass through. For this problem, the input patterns may be assumed to have at least one "X" along each edge of the pattern. The input is terminated by a line containing a single zero in place of a valid dimension.
Output
For each data set in the input, output the data set number and one of the following messages:
Valid set of patterns
Impossible combination
For a set of patterns to be considered valid, it must be possible to construct, by gluing unit cubes together along their faces, a one-piece solid capable of casting the shadow of each of the input patterns.
Sample Input
5
XXXXX
X----
X--XX
X---X
XXXXX
XXXXX
X----
XXXXX
X----
XXXXX
XXXXX
X---X
XXXX-
X---X
XXXXX
3
X--
-X-
--X
XX-
XXX
-XX
-XX
XXX
XX-
0
Sample Output
Data set 1: Valid set of patterns
Data set 2: Impossible combination
柏拉图的积木
描述
柏拉图相信我们所感知的只是现实的影子。最近的考古发掘发现的证据表明，柏拉图年轻时对设计巧妙的积木的娱乐可能鼓励了这种信念。这些积木有一个奇怪的特性，当任何一面面向光源时，它们都会投射出各种字母、数字、形状和图案的阴影。入射到一个角落的三个面可能对应三个不同的阴影图案。当然，相反的面孔会投射出彼此镜像的阴影。
这些块是通过将小立方体粘合在一起形成一个单一的、连接的对象而形成的。例如，下图逐层显示了可以投射字母“E”、“G”或“B”阴影的块的内部结构。
只发现了部分块，但好奇的科学家们想确定哪些阴影组合是可能的。你的程序，这个问题的解决方案，将帮助他们！程序将输入阴影图案组，并为每组报告是否可以构建将投射这三个阴影的实体。
输入
输入包含一系列数据集，每个数据集指定一个维度和三个阴影模式。数据集的第一行包含一个正整数 1 <= n <= 20，它指定输入模式的维度。数据集的其余部分由 3n 行组成，每行包含一个由 n 个“X”和“-”字符组成的字符串。每组 n 行代表一个模式。在出现“X”的地方，最后的实体应该投下阴影，而在出现“-”的地方，光线应该通过。对于这个问题，可以假设输入模式沿模式的每条边至少有一个“X”。输入以包含单个零代替有效维度的行终止。
输出
对于输入中的每个数据集，输出数据集编号和以下消息之一：
有效的模式集
不可能的组合
对于一组被认为有效的模式，必须可以通过将单位立方体沿着它们的方向粘合在一起来构造面，一个整体实体，能够投射每个输入模式的阴影。
Sample Input
5
XXXXX
X----
X--XX
X---X
XXXXX
XXXXX
X----
XXXXX
X----
XXXXX
XXXXX
X---X
XXXX-
X---X
XXXXX
3
X--
-X-
--X
XX-
XXX
-XX
-XX
XXX
XX-
0
Sample Output
Data set 1: Valid set of patterns
Data set 2: Impossible combination
解题思路：
读入三视图以后先枚举保存每一个面的8种情况（旋转、翻转）。
然后8*8*8枚举每一种搭配情况。在枚举这种情况的时候要做一些事情：
1.构造立体图形。构造方法很特别，不是正的构造，是反的构造（即一开始都填满，根据条件删去格子。这点很重要！也是我想不出这道题的关键瓶颈。）反的构造能直接确定哪些格子不能放。
2.判断。判断有两个方面，一方面是判断构造出来的图形是否满足三视图，另一方面判断它是否是全部连通。
代码：
#include
#include
#include
#include
using namespace std;
int sur[4][10][25][25],n;
int cube[25][25][25],vis[25][25][25];
void makesur(){
int p,i,j,k;
for (p = 0;p < 3;p ++){
for (k = 2;k <= 4;k ++)
for (i = 1;i <= n;i ++)
for (j = 1;j <= n;j ++)
sur[p][k][j][n - i + 1] = sur[p][k - 1][i][j];
for (k = 1;k <= 4;k ++)
for (i = 1;i <= n;i ++)
for (j = 1;j <= n;j ++)
sur[p][k + 4][n - i + 1][j] = sur[p][k][i][j];
}
}
void fill(int a1,int a2,int a3){
int i,j,k;
for (i = 1;i <= n;i ++)
for (j = 1;j <= n;j ++) if (!sur[0][a1][i][j])
for (k = 1;k <= n;k ++)
cube[i][j][k] = 0;
for (i = 1;i <= n;i ++)
for (j = 1;j <= n;j ++) if (!sur[1][a2][i][j])
for (k = 1;k <= n;k ++)
cube[k][i][j] = 0;
for (i = 1;i <= n;i ++)
for (j = 1;j <= n;j ++) if (!sur[2][a3][i][j])
for (k = 1;k <= n;k ++)
cube[i][k][j] = 0;
}
bool check(int a1,int a2,int a3){
int i,j,k,flag;
for (i = 1;i <= n;i ++)
for (j = 1;j <= n;j ++) if (sur[0][a1][i][j]){
flag = 0;
for (k = 1;k <= n;k ++) if (cube[i][j][k]){flag = 1;break;}
if (!flag) return 0;
}
for (i = 1;i <= n;i ++)
for (j = 1;j <= n;j ++) if (sur[1][a2][i][j]){
flag = 0;
for (k = 1;k <= n;k ++) if (cube[k][i][j]){flag = 1;break;}
if (!flag) return 0;
}
for (i = 1;i <= n;i ++)
for (j = 1;j <= n;j ++) if (sur[2][a3][i][j]){
flag = 0;
for (k = 1;k <= n;k ++) if (cube[i][k][j]){flag = 1;break;}
if (!flag) return 0;
}
return 1;
}
void dfs(int i,int j,int k){
if (i < 1 || i > n || j < 1 || j > n || k < 1 || k > n) return;
if (vis[i][j][k]) return;
if (!cube[i][j][k]) return;
vis[i][j][k] = 1;
dfs(i + 1,j,k);
dfs(i - 1,j,k);
dfs(i,j + 1,k);
dfs(i,j - 1,k);
dfs(i,j,k + 1);
dfs(i,j,k - 1);
}
bool block_chk(){
int i,j,k;
memset(vis,0,sizeof vis);
for (i = 1;i <= n;i ++)
for (j = 1;j <= n;j ++) if (cube[i][j][1]) {
dfs(i,j,1);
goto aa;
}
aa:;
for (i = 1;i <= n;i ++)
for (j = 1;j <= n;j ++)
for (k = 1;k <= n;k ++)
if (!vis[i][j][k] && cube[i][j][k]) return 0;
return 1;
}
bool solve(){
int i,j,k;
makesur();
for (i = 1;i <= 8;i ++)
for (j = 1;j <= 8;j ++)
for (k = 1;k <= 8;k ++){
memset(cube,1,sizeof cube);
fill(i,j,k);
if (check(i,j,k) && block_chk()) return 1;
}
return 0;
}
void debug(){
int p,i,j;
for (p = 0;p < 3;p ++){
for (i = 1;i <= n;i ++){
for (j = 1;j <= n;j ++){
cout << sur[p][1][i][j] << " ";
}
cout << endl;
}
cout << endl;
}
}
int main(){
int T = 0,p,i,j;
char c;
while (scanf("%d",&n),n){
for (p = 0;p < 3;p ++){
for (i = 1;i <= n;i ++){
getchar();
for (j = 1;j <= n;j ++){
c = getchar();
if (c == 'X') sur[p][1][i][j] = 1;
else sur[p][1][i][j] = 0;
}
}
}
//debug();
printf("Data set %d: ",++T);
if (solve()) puts("Valid set of patterns");
else puts("Impossible combination");
}
return 0;
}