自动搬运

查看原文

来自洛谷，原作者为

	zhylj 人生输家

搬运于2025-08-24 22:25:38，当前版本为作者最后更新于2021-12-08 22:58:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑如何判断一个二维图形是否能够折成一个正方体：随意选择一个底面放在 $Oxy$ 平面上，然后令 $z$ 轴正方向为指向正方体内部的方向。我们每次把一个面的所有相邻面都向上翻（也就是向内翻），同时递归到所有相邻面继续折，若最后没有面重合，那么就合法。

接下来考虑如何把上述做法推广到四维，假设我们放的超立方体个顶点和原点重合，其余的一些棱分别和四个坐标轴重合。记四个坐标轴分别为 $x,y,z,w$，我们随便选一个正方体放在 $Oxyz$ 空间中，然后把其它立方体向“上”翻，然后变换一下坐标系使得 $w$ 轴始终朝内，当前立方体始终在 $Oxyz$ 空间内。

维护垂直于 $x,y,z,w$ 轴的立方体，不难发现这样的立方体有两个，两两一组都垂直于其中一个坐标轴，我们只需要记一下其中离原点最近的一个的编号即可，接下来我们考虑某个坐标轴上的两个分别向内翻折的情况，以 $x$ 轴为例：

• 取的是 $x$ 轴上远离原点的向内翻折，则以新立方体为底面的内侧在 $x$ 轴的反方向，但 $x$ 轴上新的离原点最近的立方体变成了原先离原点最远的立方体。

• 取的是 $x$ 轴上靠近原点的向内翻折，则以新立方体为底面的内侧在 $x$ 轴的正方向，但 $w$ 轴也跟着转了，于是 $w$ 轴上新的离原点最近的立方体变成了原先离原点最远的立方体。

• 其他维同理。

不难写个 DFS 解决问题。

const int N = 10;

int m, n, k, v_cnt, p[N], vis[N];
char str[N][N][N];

void Dfs(int x, int y, int z, int a, int b, int c, int d) {
	str[x][y][z] = '.';
	++vis[d];
	if(str[x + 1][y][z] == 'x') Dfs(x + 1, y, z, d ^ 1, b, c, a);
	if(str[x - 1][y][z] == 'x') Dfs(x - 1, y, z, d, b, c, a ^ 1);
	if(str[x][y + 1][z] == 'x') Dfs(x, y + 1, z, a, d ^ 1, c, b);
	if(str[x][y - 1][z] == 'x') Dfs(x, y - 1, z, a, d, c, b ^ 1);
	if(str[x][y][z + 1] == 'x') Dfs(x, y, z + 1, a, b, d ^ 1, c);
	if(str[x][y][z - 1] == 'x') Dfs(x, y, z - 1, a, b, d, c ^ 1);
}

int main() {
	rd(m, n, k);
	for(int x = 1; x <= k; ++x)
		for(int y = 1; y <= n; ++y)
			scanf("%s", str[x][y] + 1);
	for(int x = 1; x <= k; ++x)
		for(int y = 1; y <= n; ++y)
			for(int z = 1; z <= m; ++z)
				if(str[x][y][z] == 'x') {
					Dfs(x, y, z, 0, 2, 4, 6);
					bool flag = true;
					for(int i = 0; i < 8; ++i)
						if(vis[i] != 1) {
							flag = false;
							break;
						}
					if(flag) printf("Yes\n");
					else printf("No\n");
					return 0;
				}
	return 0;
}