UVa 253 Cube Painting

题目分析

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

问题本质

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

输入输出格式

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

示例分析

以输入rbgggrrggbgr为例：

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

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

解题思路

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

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

1. 先选择一个面作为顶面（666种选择）
2. 再选择该面的一个朝向（444种旋转）

因此总共有6×4=246 \times 4 = 246×4=24种旋转。

2. 面编号约定

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

3. 解法选择

本题有几种常见解法：

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

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

4.242424种旋转的生成方法

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

1. 以面111为顶面，面666为底面，枚举444种水平旋转。
2. 将立方体翻转，使其他面成为顶面，重复上述过程。

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

5. 算法步骤

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

6. 复杂度分析

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

实现细节

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

• 题目的面编号为1∼61 \sim 61∼6，而C/C++中字符串索引从000开始，因此使用时需要减111。
• 映射的含义：transform[i][j]表示原始立方体中编号为transform[i][j]的面，在旋转后位于位置j+1j+1j+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>usingnamespacestd;intmain(){cin.tie(0);cin.sync_with_stdio(false);// 预定义的 24 种旋转映射// 每个映射是一个长度为 6 的排列，表示原始立方体各面在旋转后的新位置// 映射值对应面的编号（1~6），使用时需要转换为索引（减 1）inttransform[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);boolfound=false;// 枚举所有 24 种旋转for(inti=0;i<24;i++){string temp;// 根据当前旋转映射，生成旋转后的颜色排列for(intj=0;j<6;j++)temp.append(1,first[transform[i][j]-1]);// 映射值减 1 转换为索引// 如果旋转后与第二个立方体一致，则匹配成功if(temp==second){found=true;break;}}// 输出结果if(found)cout<<"TRUE\n";elsecout<<"FALSE\n";}return0;}

总结

本题核心在于理解立方体的242424种旋转方向。通过预计算所有旋转映射，我们可以用非常简单的代码解决该问题。这种方法直观、高效，且易于调试和验证。

对于初学者来说，掌握这种“预计算 + 枚举”的思路，对于解决类似的组合数学和几何变换问题非常有帮助。