P6980

zhylj · 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;
}