U614083 二阶魔方还原步数计算

二阶魔方（Pocket Cube）是 2×2×2 的立方体结构，由 8 个角块组成，每个角块包含 3 种不同颜色。魔方的每个面可以绕其中心轴旋转 90 度（顺时针或逆时针），每完成一次这样的旋转记为 “一步”。

给定一个二阶魔方的当前状态，请计算将其还原为 “标准还原态” 所需的最少步数。 ### 标准还原态定义 标准还原态的六个面颜色及角块分布固定，具体如下（角块按 “所属面首字母组合” 标识，颜色对应为面的默认颜色）： 上面（U 面）：颜色为白色（W），顺时针顺序角块：UFL（WRG）、UFR（WRB）、UBR（WOB）、UBL（WOG） 下面（D 面）：颜色为黄色（Y），顺时针顺序角块：DFL（YRG）、DFR（YRB）、DBR（YOB）、DBL（YOG） 前面（F 面）：颜色为红色（R），顺时针顺序角块：UFL（WRG）、UFR（WRB）、DFR（YRB）、DFL（YRG） 右面（R 面）：颜色为蓝色（B），顺时针顺序角块：UFR（WRB）、UBR（WOB）、DBR（YOB）、DFR（YRB） 左面（L 面）：颜色为绿色（G），顺时针顺序角块：UBL（WOG）、UFL（WRG）、DFL（YRG）、DBL（YOG） 后面（B 面）：颜色为橙色（O），顺时针顺序角块：UBR（WOB）、UBL（WOG）、DBL（YOG）、DBR（YOB） 其中，角块的字符串表示（如WRG）由三个面的颜色首字母组成，对应角块所属三个面的默认颜色（例如WRG对应 U 面白、F 面红、L 面绿）。

输入共 6 行，按固定顺序对应魔方的 6 个面：第 1 行 U 面、第 2 行 D 面、第 3 行 F 面、第 4 行 R 面、第 5 行 L 面、第 6 行 B 面。每行包含 4 个字符串（每个字符串 3 个大写字母），表示对应面按顺时针顺序排列的 4 个角块（角块顺序与 “标准还原态” 一致）。

输出一个整数，表示将给定状态还原为标准还原态所需的最少步数（每步为单个面的 90 度顺时针或逆时针旋转）。

二阶魔方的 “上帝之数”（最坏情况下的最少还原步数）为 14 步（按本题 “90 度顺 / 逆为一步” 的定义），因此 BFS 的搜索深度上限为 14，效率可控。 核心解法思路：使用广度优先搜索（BFS），以 “当前魔方状态” 为节点，“单个面的 90 度旋转（顺 / 逆）” 为边，从给定状态出发，逐层搜索直到找到标准还原态，此时的层数即为最少步数。 状态去重：由于魔方状态数量有限（共 3674160 种），需将每个状态哈希为唯一标识（如拼接 6 行字符串为一个长字符串），用哈希表（如 Python 的set）记录已访问状态，避免重复搜索。 旋转模拟：需预先定义 6 个面的顺时针 / 逆时针旋转规则（如 R 面顺时针旋转时，其 4 个角块的位置置换为(UFR→UBR→DBR→DFR→UFR)），旋转后生成新的魔方状态。