UVa 253 Cube Painting

寂静山林

73人浏览 · 2026-05-21 12:22:32

寂静山林 · 2026-05-21 12:22:32 发布

题目分析

本题的核心问题是：给定两个涂色立方体，每个立方体有 $6$ 个面，每个面被涂上蓝色（b）、红色（r）或绿色（g）中的一种颜色。立方体的面按照固定的编号排列。我们需要判断两个立方体是否可以通过旋转（不包括反射）使得涂色方案完全相同。

问题本质

这是一个典型的 立方体旋转等价类判定 问题。由于立方体有 $24$ 种不同的旋转方向（旋转群的大小为 $24$ ），我们需要检查第一个立方体经过某种旋转后，其 6 个面的颜色排列是否与第二个立方体完全一致。

输入输出格式

输入文件每行包含 $12$ 个字符，前 $6$ 个字符表示第一个立方体（面 $1$ 到面 $6$ 的颜色），后 $6$ 个字符表示第二个立方体。
对于每一行，如果两个立方体可以通过旋转相互转换，输出 TRUE，否则输出 FALSE。

示例分析

以输入 rbgggrrggbgr 为例：

第一个立方体： rbgggr
第二个立方体： rggbgr

题目说明，将第一个立方体绕垂直轴旋转 $90°$ 后，就变成了第二个立方体，因此输出 TRUE。

解题思路

1. 立方体旋转的数学基础

一个立方体有 $24$ 种不同的旋转方向。这 $24$ 种旋转可以通过以下方式生成：

先选择一个面作为顶面（ $6$ 种选择）
再选择该面的一个朝向（ $4$ 种旋转）

因此总共有 $\times 4 = 24$ 种旋转。

2. 面编号约定

题目中面的编号如图 $1$ 所示，但我们不需要知道具体编号，只需要知道旋转后原来的第 $i$ 个面会移动到哪个位置。

3. 解法选择

本题有几种常见解法：

枚举所有 $24$ 种旋转：预计算每个旋转对应的面索引映射，然后逐一检查。
$BFS/DFS\texttt{BFS/DFS}$ 搜索旋转：从初始状态出发，通过旋转生成所有可能的状态，然后判断目标状态是否在集合中。
立方体着色标准化：将立方体旋转到某个“标准方向”，然后比较标准化后的字符串。

其中最直接、最简单的是 枚举 $24$ 种旋转。

4. $24$ 种旋转的生成方法

我们可以手动推导或通过程序生成所有 $24$ 种旋转。常用的方法是：

以面 $1$ 为顶面，面 $6$ 为底面，枚举 $4$ 种水平旋转。
将立方体翻转，使其他面成为顶面，重复上述过程。

最终得到 $24$ 个映射表，每个映射表是一个长度为 $6$ 的排列，表示原始编号 $\sim 6$ 旋转后的新位置编号。

5. 算法步骤

读取输入的每一行。
将前 $6$ 个字符保存为 first，后 $6$ 个字符保存为 second。
对于 $24$ 种旋转中的每一种：
- 根据旋转映射，从 first 生成旋转后的颜色字符串 temp。
- 如果 temp 等于 second，则标记为匹配并退出循环。
根据是否匹配输出 TRUE 或 FALSE。

6. 复杂度分析

每个立方体有 $6$ 个面，旋转映射检查为 $O (6)$ 。
$24$ 种旋转，总操作数为 $24 \times 6 = 144$ 次字符比较，对于输入规模完全可以忽略不计。

实现细节

在代码中，我们预定义了 transform[24][6]，存储了 $24$ 种旋转映射。注意：

题目的面编号为 $\sim 6$ ，而 C/C++ 中字符串索引从 $0$ 开始，因此使用时需要减 $1$ 。
映射的含义：transform[i][j] 表示原始立方体中编号为 transform[i][j] 的面，在旋转后位于位置 $j + 1$ 。

例如，第一个映射 {1, 2, 3, 4, 5, 6} 表示恒等旋转，各面位置不变。

代码实现

// Cube Painting
// UVa ID: 253
// Verdict: Accepted
// Submission Date: 2016-05-10
// UVa Run Time: 0.000s
//
// 版权所有（C）2016，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);

    // 预定义的 24 种旋转映射
    // 每个映射是一个长度为 6 的排列，表示原始立方体各面在旋转后的新位置
    // 映射值对应面的编号（1~6），使用时需要转换为索引（减 1）
    int transform[24][6] = {
        {1, 2, 3, 4, 5, 6}, {1, 4, 2, 5, 3, 6},
        {1, 5, 4, 3, 2, 6}, {1, 3, 5, 2, 4, 6},
        {2, 6, 3, 4, 1, 5}, {2, 4, 6, 1, 3, 5},
        {2, 1, 4, 3, 6, 5}, {2, 3, 1, 6, 4, 5},
        {3, 1, 2, 5, 6, 4}, {3, 2, 6, 1, 5, 4},
        {3, 6, 5, 2, 1, 4}, {3, 5, 1, 6, 2, 4},
        {4, 1, 5, 2, 6, 3}, {4, 5, 6, 1, 2, 3},
        {4, 6, 2, 5, 1, 3}, {4, 2, 1, 6, 5, 3},
        {5, 1, 3, 4, 6, 2}, {5, 3, 6, 1, 4, 2},
        {5, 6, 4, 3, 1, 2}, {5, 4, 1, 6, 3, 2},
        {6, 2, 4, 3, 5, 1}, {6, 4, 5, 2, 3, 1},
        {6, 5, 3, 4, 2, 1}, {6, 3, 2, 5, 4, 1}
    };

    string line;
    while (getline(cin, line))
    {
        // 分割输入字符串，前 6 个字符为第一个立方体，后 6 个字符为第二个立方体
        string first = line.substr(0, 6);
        string second = line.substr(6, 6);

        bool found = false;
        // 枚举所有 24 种旋转
        for (int i = 0; i < 24; i++)
        {
            string temp;
            // 根据当前旋转映射，生成旋转后的颜色排列
            for (int j = 0; j < 6; j++)
                temp.append(1, first[transform[i][j] - 1]); // 映射值减 1 转换为索引

            // 如果旋转后与第二个立方体一致，则匹配成功
            if (temp == second)
            {
                found = true;
                break;
            }
        }

        // 输出结果
        if (found)
            cout << "TRUE\n";
        else
            cout << "FALSE\n";
    }

    return 0;
}