P6980 [NEERC 2015] Hypercube

考虑一个 $4$-超立方体，也称为四维超正方体。一个单位实心四维超正方体是一个四维图形，它等于 $16$ 个点的凸包，这些点的笛卡尔坐标为 $(\pm\frac{1}{2}, \pm\frac{1}{2}, \pm\frac{1}{2}, \pm\frac{1}{2})$，即它的顶点。它有 $32$ 条边（$1D$），$24$ 个正方形面（$2D$），以及 $8$ 个立方体 $3$-面（$3D$），也称为单元。我们研究空心四维超正方体，并将四维超正方体定义为一个实心四维超正方体的边界。因此，四维超正方体是 $8$ 个实心立方体（其单元）的连接联合，这些立方体在四维超正方体的 $24$ 个正方形面、$32$ 条边和 $16$ 个顶点之间相交。 让我们沿着四维超正方体的 $24$ 个面中的 $17$ 个面切割它，使其仍然通过剩下的 $7$ 个未被切割的面保持连接。通过沿着未被切割的面旋转其构成立方体，将四维超正方体展开到三维超平面中，直到其所有单元都位于同一三维超平面中。结果称为四维超正方体的 $3$-网。这一过程是三维立方体如何被切割并展开到二维平面上以产生由 $6$ 个正方形组成的立方体的 $2$-网的自然推广。 在这个问题中，给定一个树状的 $8$-多立方体，也称为八立方体。八立方体是由 $8$ 个单位立方单元面对面连接而成的集合。更正式地说，构成八立方体的每对立方单元的交集要么为空，要么是一个点、一个单位线（$1D$），或一个单位正方形（$2D$）。给定的八立方体在以下意义上是树状的。考虑八立方体的邻接图——一个有 $8$ 个顶点的图，对应于其 $8$ 个单元。邻接图中存在一条边连接相邻单元对。当两个八立方体的单元的交集是一个正方形时，它们被称为相邻。当它们在一个点或一条线上相交时，不被认为是相邻的。当其邻接图是树时，八立方体被称为树状。 你的任务是确定给定的树状八立方体是否构成四维超正方体的 $3$-网。也就是说，这个八立方体是否可以放置在四维空间的超平面上，并沿其单元之间的交叉正方形在四维空间中折叠成一个四维超正方体。 例如，看看下面最左边的图片。它显示了树状八立方体的线框。将单元 $GHLKG_{1}H_{1}L_{1}K_{1}$ 绕平面 $GHLK$ 旋转，将单元 $FGKJF_{2}G_{2}K_{2}J_{2}$ 绕平面 $FGKJ$ 在第四维度上旋转 $90$ 度，超出原始超平面。结果，点 $G_{1}$ 与 $G_{2}$ 结合，$K_{1}$ 与 $K_{2}$ 结合。面 $GKK_{2}G_{2}$ 粘合到面 $GKK_{1}G_{1}$。结果如右图所示。第四维度正交投影到所示的三维透视图中。那些从原始超平面移出的点用空心点标记。  旋转 $EFJIE_{1}F_{1}J_{1}I_{1}$ 绕 $EFJI$，旋转 $EHLIE_{2}H_{2}L_{2}I_{2}$ 绕 $EHLI$。结果如下面左图所示。剩下的步骤如下。绕 $MNOPQRST$ 旋转，然后绕 $IJKL$ 旋转 $MNOPQRST$ 和 $IJKLMNOP$，最后绕 $EFGH$ 旋转 $ABCDEFGH$。最后一步是将所有相遇的面粘合在一起，得到右图所示的四维超正方体。 

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

输出文件中写入一个单词 `Yes`，如果给定的八立方体可以折叠成一个四维超正方体，否则写入 `No`。

时间限制：1 秒，内存限制：256 MB。 题面翻译由 ChatGPT-4o 提供。