QOJ.ac

QOJ

Time Limit: 2.0 s Memory Limit: 256 MB Total points: 100

#12554. 超立方体

Statistics

考虑一个 4-超立方体,也称为超正方体(tesseract)。一个单位实心超正方体是一个 4D 图形,等同于 16 个笛卡尔坐标为 $(\pm\frac{1}{2}, \pm\frac{1}{2}, \pm\frac{1}{2}, \pm\frac{1}{2})$ 的点的凸包,这些点即为其顶点。它有 32 条边(1D)、24 个正方形面(2D)和 8 个立方体 3-面(3D),也称为胞(cells)。我们研究空心超正方体,并将超正方体定义为实心超正方体的边界。因此,超正方体是 8 个实心立方体(其胞)的连通并集,它们在 24 个超正方体的正方形面、32 条边和 16 个顶点处相互交汇。

让我们沿着超正方体的 24 个面中的 17 个进行切割,使其仍然通过保留的 7 个面保持连通。通过沿着保留的面旋转其构成的立方体,将超正方体展开到一个 3D 超平面中,直到其所有胞都位于同一个 3D 超平面内。其结果被称为超正方体的 3-网(3-net)。这个过程是 3D 立方体如何被切割并展开到 2D 平面上以产生由 6 个正方形组成的 2-网的自然推广。

在本题中,给定一个 3D 空间中的树状 8-多方块(8-polycube),也称为八方块(octocube)。八方块是由 8 个面面相连的单位立方体胞组成的集合。更正式地说,构成八方块的每一对立方体胞的交集要么为空,要么是一个点、一条单位线段(1D)或一个单位正方形(2D)。给定的八方块在以下意义上是树状的:考虑八方块的邻接图——一个具有 8 个顶点(对应于其 8 个胞)的图。如果一对胞相邻,则邻接图中存在一条边。当两个八方块胞的交集是一个正方形时,称它们相邻。在点或线处相交的胞不被视为相邻。当八方块的邻接图是一棵树时,称其为树状的。

你的任务是确定给定的树状八方块是否构成超正方体的 3-网。也就是说,这个八方块放置在 4D 空间的一个超平面上后,能否在 4D 空间中沿着其胞之间的交集正方形折叠成一个超正方体。

例如,看下面左侧的图片。它展示了树状八方块的线框图。将胞 $GHLKG_1H_1L_1K_1$ 绕平面 $GHLK$ 旋转,并将胞 $FGKJF_2G_2K_2J_2$ 绕平面 $FGKJ$ 在原始超平面之外的第 4 维度旋转 90 度。结果,点 $G_1$ 与 $G_2$ 重合,$K_1$ 与 $K_2$ 重合。面 $GKK_2G_2$ 与面 $GKK_1G_1$ 粘合。结果显示在右侧。第 4 维度被正交投影到透视显示的 3 个维度上。移出原始超平面的点用空心圆点标记。

旋转 $EFJIE_1F_1J_1I_1$ 绕 $EFJI$ 和 $EHLIE_2H_2L_2I_2$ 绕 $EHLI$。结果显示在左侧的下图中。其余步骤如下。将 $MNOPQRST$ 绕 $MNOP$ 旋转,然后将 $MNOPQRST$ 和 $IJKLMNOP$ 同时绕 $IJKL$ 旋转,并将 $ABCDEFGH$ 绕 $EFGH$ 旋转。最后一步是将所有相遇的面粘合在一起,得到右侧所示的超正方体。

输入格式

输入文件的第一行包含三个整数 $m, n, k$ —— 包含给定八方块的盒子的宽度、深度和高度($1 \le m, n, k \le 8$)。接下来的 $k$ 组行描述了从上到下盒子的矩形切片。每个切片由 $n$ 行描述,每行包含 $m$ 个字符。行上的字符要么是 ‘.’,表示空空间,要么是 ‘x’,表示一个单位立方体。保证输入文件描述的是一个树状八方块。

输出格式

如果给定的八方块可以折叠成超正方体,则向输出文件写入单词 “Yes”,否则写入 “No”。

样例

样例输入 1

3 3 4
...
.x.
...
.x.
xxx
.x.
...
.x.
...
...
.x.
...

样例输出 1

Yes

样例输入 2

8 1 1
xxxxxxxx

样例输出 2

No

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.