#513. 三阶魔方
三阶魔方
题目背景
灰太狼学长最近正在备战考研。一次刷题间隙,他本想随手转几下三阶魔方放松一下,却无意间迷上了研究魔方公式。
他发现:从还原状态出发,不断重复执行同一套公式,魔方最终总会回到最初的状态。例如,公式 U 连续执行 次后会恢复原状;公式 UU 连续执行 次后就会恢复原状。
为了弄清一套公式究竟会占用多少个“复习间隙”,灰太狼学长想请你计算:至少完整执行多少遍给定公式,魔方才会第一次恢复原状?
问题描述
一颗三阶魔方的表面共有 个色块位置,编号为 到 。为了精确记录魔方状态,我们也给这 个色块分别编号 到 。开始时,第 号色块位于第 号位置;只有当每个编号色块都回到自己的初始位置时,才称魔方恢复原状。
给定一个仅由 U、D、L、R、F、B 组成的非空字符串 。字符串中的每个字符表示:从魔方外侧正对相应面观察时,将该面所在的一层顺时针旋转 。
六种操作分别表示:
| 操作 | 含义 |
|---|---|
U |
上面所在的一层顺时针旋转 |
D |
下面所在的一层顺时针旋转 |
L |
左面所在的一层顺时针旋转 |
R |
右面所在的一层顺时针旋转 |
F |
前面所在的一层顺时针旋转 |
B |
后面所在的一层顺时针旋转 |
魔方色块位置的展开图如下。每个面的编号均按照图中方向排列:
+----------+
| 0 1 2 |
| 3 4 5 | U
| 6 7 8 |
+----------+
+----------+-------------+----------+-------------+
| 18 19 20 | 36 37 38 | 27 28 29 | 45 46 47 |
| 21 22 23 | 39 40 41 | 30 31 32 | 48 49 50 |
| 24 25 26 | 42 43 44 | 33 34 35 | 51 52 53 |
| L | F | R | B |
+----------+-------------+----------+-------------+
+----------+
| 9 10 11 |
| 12 13 14 | D
| 15 16 17 |
+----------+
为使旋转规则完全明确,下表给出了六种操作对应的置换环。记号 表示一次操作后:位置 上的色块移动到位置 ,位置 上的色块移动到位置 ,位置 上的色块移动到位置 ,位置 上的色块移动到位置 。同一行中的所有置换环同时发生,未列出的位置保持不变。
| 操作 | 置换环 |
|---|---|
U |
$(0\ 2\ 8\ 6)(1\ 5\ 7\ 3)(18\ 45\ 27\ 36)(19\ 46\ 28\ 37)(20\ 47\ 29\ 38)$ |
D |
$(9\ 11\ 17\ 15)(10\ 14\ 16\ 12)(24\ 42\ 33\ 51)(25\ 43\ 34\ 52)(26\ 44\ 35\ 53)$ |
L |
$(0\ 36\ 9\ 53)(3\ 39\ 12\ 50)(6\ 42\ 15\ 47)(18\ 20\ 26\ 24)(19\ 23\ 25\ 21)$ |
R |
$(2\ 51\ 11\ 38)(5\ 48\ 14\ 41)(8\ 45\ 17\ 44)(27\ 29\ 35\ 33)(28\ 32\ 34\ 30)$ |
F |
$(6\ 27\ 11\ 26)(7\ 30\ 10\ 23)(8\ 33\ 9\ 20)(36\ 38\ 44\ 42)(37\ 41\ 43\ 39)$ |
B |
$(0\ 24\ 17\ 29)(1\ 21\ 16\ 32)(2\ 18\ 15\ 35)(45\ 47\ 53\ 51)(46\ 50\ 52\ 48)$ |
每一遍都必须从头到尾完整执行一次字符串 。请求出最小正整数 ,使得连续执行 遍 后,每个色块都回到初始位置。
你需要独立回答 组询问。每组询问开始时,魔方都会重新处于初始状态。
输入格式
第一行包含一个整数 ,表示询问数量。
接下来 行,每行包含一个非空字符串 ,表示一套魔方公式。
输出格式
对于每组询问,输出一行一个整数,表示魔方第一次恢复原状时,公式 需要被完整执行的遍数。
数据范围
。
,且所有询问的字符串长度之和不超过 。
仅由大写字母 U、D、L、R、F、B 组成。
样例
输入数据 1
3
U
UU
UUUU
输出数据 1
4
2
1
样例解释
- 对于
U,同一层需要旋转 次才能回到原位。 - 对于
UU,完整执行一遍相当于旋转 ,因此执行 遍后恢复原状。 - 对于
UUUU,完整执行一遍后魔方就已经恢复原状,所以答案为 。
输入数据 2
3
UR
FUL
LUF
输出数据 2
105
80
84
这组样例说明,不同面的旋转复合后可能产生较长的循环,并且改变操作顺序可能改变答案。
时间限制: 不超过 ; 不超过 ; 不超过 。
内存限制: 不超过 ; 不超过 ; 不超过 。