poj 1022 Packing Unit 4D Cubes
Packing Unit 4D Cubes
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 2946 | Accepted: 1048 |
Description
We usually think that there are three geometric dimensions; the fourth dimension is usually time. However, the Association for Customizing Machines (ACM) has to deal with four geometrical dimensions for their strange customer EE3 who needs to pack four dimensional products into perpendicular parallelepipeds before shipping them to the newly emerged market niche just on the outskirts of the Milky Way.
Each of EE3 products consists of a number of unit 4D cubes that are glued together at their faces. A face of a 4D cube is a 3D cube and each 4D cube has 8 such faces. The picture on the left shows a 4D cube projected into a plane with the four principal, orthogonal axes shown. It takes a bit of effort to stretch our imagination and see the faces of a 4D cube in such a projection. The pictures below try to illustrate how the two faces along each of the four axes are situated in 4D. Again, using just the planar projection it is not so easy to illustrate and takes some effort to see. But we have done a good job, didn't we?
Each EE3 product to be packed consists of a number of unit 4D cubes that are glued together along their faces which are 3D cubes. Your job is simple: find the minimal volume measured in the number of unit 4D cubes of a perpendicular parallelepiped (a 4D box) into which the product can be packed before shipping.
Input
The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by input data for each test case describing one EE3 product. The first line of each test case is an integer n (1 ≤ n ≤ 100) which is the number of unit 4D cubes used in the product. Next, there are n lines, each describing one unit cube and contains 9 nonnegative integer numbers.
The first number, a positive integer, is the unique identifier of a cube and the remaining 8 numbers give the identities of neighbors of the cube listed in the following order:
?the first two numbers are identifiers of the cubes glued to the opposing sides of the given cube along the x1 axis as seen looking in the direction of the x1 axis;
?the next two numbers as above but for the x2 axis;
?the next two numbers as above but for the x3 axis;
?the next two numbers as above but for the x4 axis;
If a cube does not have a neighbor glued to one of its faces we use 0 instead of a cube identifier.
The problem is that the employees of ACM may produce inconsistent descriptions of EE3 products. There are two sources of such inconsistencies:
?A consistent description must be symmetric, i.e. if cube x is glued to cube y at some face then cube y must be glued to cube x at the corresponding face along the same axis. The following description is inconsistent:
3 0 0 1 0 0 0 0 0
1 0 0 3 0 0 0 0 0
?Any description must describe a single solid, i.e. there must be only one component in the product. Thus the following is inconsistent:
1 2 0 0 0 0 0 0 0
2 0 1 0 0 0 0 0 0
3 0 0 4 0 0 0 0 0
4 0 0 0 3 0 0 0 0
Output
There should be one output line per test case containing either the number of unit 4D cubes in the smallest 4D perpendicular parallelepiped oriented along the axes into which the product can be packed if the description is consistent, or the word Inconsistent, otherwise.
Sample Input
1
9
1 2 3 4 5 6 7 8 9
2 0 1 0 0 0 0 0 0
3 1 0 0 0 0 0 0 0
4 0 0 0 1 0 0 0 0
5 0 0 1 0 0 0 0 0
6 0 0 0 0 0 1 0 0
7 0 0 0 0 1 0 0 0
8 0 0 0 0 0 0 0 1
9 0 0 0 0 0 0 1 0
Sample Output
81
包装单元四维立方体
描述
我们通常认为有三个几何维度;第四维度通常是时间。然而，定制机器协会(ACM)必须为他们奇怪的客户EE3处理四个几何尺寸，他们需要将四维的产品打包成垂直的平行六面体，然后将它们运送到刚刚在银河系边缘出现的小市场。
每一个EE3产品都由许多单元四维立方体组成，这些立方体是粘在一起的。四维立方体的一个面是一个三维立方体，每个四维立方体有8个这样的面。左边的图片显示了一个四维立方体投射到一个平面上，显示了四个主要的、正交的轴。这需要一点努力来扩展我们的想象力，并在这样的投影中看到一个四维立方体的面。下面的图片试图说明如何沿着每一个轴的两个面是在4D。同样，仅仅使用平面投影并不容易说明，需要花费一些精力才能看到。但我们做得很好，不是吗?
每一个要包装的EE3产品由许多单元四维立方体组成，这些立方体是沿其表面粘在一起的，它们是三维立方体。你的工作很简单:找到最小体积，以单位四维立方体的数量的垂直平行六面体(一个四维盒)的产品可以装进运输前。
输入
输入文件的第一行包含单个整数t(1≤t≤10)，测试用例的数量，然后是描述一个EE3产品的每个测试用例的输入数据。每个测试用例的第一行是整数n(1≤n≤100)，这是产品中使用的单元四维立方体的数量。接下来，有n行，每一行描述一个单元立方体，包含9个非负整数。
第一个数字，一个正整数，是一个立方体的唯一标识符，其余8个数字给出了立方体的邻居的标识符，按以下顺序列出:
前两个数字是立方体的标识符，它们沿着x1轴粘在给定立方体的相对两侧，就像在x1轴的方向上看到的那样;
下面的两个数如上所示，但在x2轴;
下面的两个数如上所示，但为x3轴;
下面两个数字如上所示，但为x4轴;
如果一个多维数据集没有一个邻接在它的一个面上，我们就使用0而不是一个多维数据集标识符。
问题在于ACM员工对EE3产品的描述可能不一致。这种不一致有两个来源:
一致的描述必须是对称的，例如，如果立方体x在某个面粘在立方体y上，那么立方体y必须沿同一轴在相应面粘在立方体x上。以下描述不一致:
3 0 0 1 0 0 0 0
1 0 0 3 0 0 0 0
任何描述都必须描述单个固体，即产品中必须只有一种成分。因此，以下是不一致的:
1 2 0 0 0 0 0 0
2 0 1 0 0 0 0 0
3 0 0 4 0 0 0 0
4 0 0 0 3 0 0 0
输出
每个测试用例应该有一个输出行，包含单元四维立方体的数量，如果描述是一致的，则在最小四维垂直平行六面体中，如果描述是一致的，则可以将产品装入其中;否则，则包含单词不一致的。
Sample Input
1
9
1 2 3 4 5 6 7 8 9
2 0 1 0 0 0 0 0 0
3 1 0 0 0 0 0 0 0
4 0 0 0 1 0 0 0 0
5 0 0 1 0 0 0 0 0
6 0 0 0 0 0 1 0 0
7 0 0 0 0 1 0 0 0
8 0 0 0 0 0 0 0 1
9 0 0 0 0 0 0 1 0
Sample Output
81
代码：
#include
#define MAXN 1111
int main()
{
int t;
for(scanf("%d", &t);t--;)
{
int n;
scanf("%d", &n);
int id[MAXN];
int map[MAXN][8]={0};
for(int i=0; i {
scanf("%d", &id[i]);
for(int j=0; j<8; ++j)
{
scanf("%d", &map[id[i]][j]);
}
}
bool flag[MAXN]={false}, check=true;
int queue[MAXN], head=0, tail=0;
queue[tail++] = id[0];
flag[id[0]] = true;
int maxh[MAXN][8]={0};
while(head int idx=queue[head++];
for(int l=0; l<8; ++l)
{
int p=map[idx][l];
if(p==0)
{
continue;
}
int ll=l%2?l-1:l+1;
if(map[p][ll]!=idx)
{
check=false;
break;
}
if(flag[p])
continue;
queue[tail++]=p;
flag[p]=true;
for(int j=0; j<8; ++j)
maxh[p][j]=maxh[idx][j];
maxh[p][l]=maxh[idx][l]+1;
}
if(!check)
break;
}
if(tail check=false;
if(!check)
{
printf("Inconsistent\n");
continue;
}
int ans=1;
for(int j=0; j<4; ++j)
{
int maxlen1=0, maxlen2=0;
for(int i=0; i {
int idx=id[i];
maxlen1=maxh[idx][2*j]>maxlen1?maxh[idx][2*j]:maxlen1;
maxlen2=maxh[idx][2*j+1]>maxlen2?maxh[idx][2*j+1]:maxlen2;
}
ans*=maxlen2+maxlen1+1;
}
printf("%d\n", ans);
}
return 0;
}