2017年第八届蓝桥杯 - 省赛 - C/C++大学A组 - C. 魔方状态

魔方状态

二阶魔方就是只有2层的魔方，只由8个小块组成。

小明很淘气，他只喜欢3种颜色，所有把家里的二阶魔方重新涂了颜色，如下：

前面：橙色 右面：绿色 上面：黄色 左面：绿色 下面：橙色 后面：黄色

请你计算一下，这样的魔方被打乱后，一共有多少种不同的状态。

如果两个状态经过魔方的整体旋转后，各个面的颜色都一致，则认为是同一状态。

请提交表示状态数的整数，不要填写任何多余内容或说明文字。

Ideas

这道题相对来说比较麻烦，而且比赛的时候放在第三题，有点恐怖，建议如果比赛的时候遇到这种填空题，20分钟解决不出来就跳过吧。

如果想要解决这道题，首先面临的第一个问题就是，魔方是三维，我们怎么用计算机语言进行表示。

二阶魔方是由八个块组成的，我们先给这8个块进行编号，上面四个块编号为03，下面四个块编号为47。

然后对于每一个块，都有六个面，其中有三个面是有颜色，另外三个面在魔方内部，是看不见的，所以我们还要对每一个面进行编号。

编号为0的块，它的6个面可以表示为['o', 'y', 'x', 'x', 'g', 'x']，其中o表示橙色，y表示黄色，g表示绿色，x表示看不见。

接下来我们就可以用一个二维字符数组表示一个二阶魔方：

cube = [['o', 'y', 'x', 'x', 'g', 'x'], ['o', 'y', 'g', 'x', 'x', 'x'], ['x', 'y', 'g', 'x', 'x', 'y'], ['x', 'y', 'x', 'x', 'g', 'y'], ['o', 'x', 'x', 'o', 'g', 'x'], ['o', 'x', 'g', 'o', 'x', 'x'], ['x', 'x', 'g', 'o', 'x', 'y'], ['x', 'x', 'x', 'o', 'g', 'y']] 

魔方的状态表示完了之后，接下来就要转动，进行状态转移。

玩过魔方的应该都知道，它的状态转移其实只需要通过三种旋转就可以达到：上面旋转（U）、右面旋转（R）、前面旋转（F）。

假如对于上面旋转（U）操作，首先0、1、2、3四个块的位置要交换。

0 -> 3
3 -> 2
2 -> 1
1 -> 0

然后每个块的6个面编码也要变换：

0 -> 4
4 -> 5
5 -> 2
2 -> 0

同理我们可以得出剩下两种旋转对应的块和面的变换，这样我们就得到了魔方状态转移的步骤。

接下来我们就要进行搜索了，得到魔方的所有状态。

对于某一种状态，它有R、U、F三种操作，通过每一种操作可以得到一个新的状态，而对于每一种状态，要判断一下之前有没有出现过，如果没有，添加到状态集合中，并且后面要基于这种状态继续搜索。

所以这类似于一个BFS的问题，我们需要通过队列来辅助实现。

另外题目中说“如果两个状态经过魔方的整体旋转后，各个面的颜色都一致，则认为是同一状态”，其实就是我们进行去重的依据，还需要定义一个辅助函数进行魔方的整体旋转。

定义函数try_add，传入一个魔方的状态，然后进行整体旋转操作，同样类似于面的旋转操作，不同的是三个面都要进行整体旋转。

Code Python

from collections import deque from copy import deepcopy def process_cube(state) -> str: return ''.join([''.join(x) for x in state]) def u(state): # 上面顺时针旋转一次 def u_cell(cell): # 上面顺时针旋转一次对应的每个块的面编码变化 cell[4], cell[5], cell[2], cell[0] = cell[0], cell[4], cell[5], cell[2] for i in [0, 1, 2, 3]: u_cell(state[i]) state[0], state[1], state[2], state[3] = state[1], state[2], state[3], state[0] return state def r(state): # 右面顺时针旋转一次 def r_cell(cell): # 右面顺时针旋转一次对应的每个块的面编码变化 cell[0], cell[1], cell[5], cell[3] = cell[3], cell[0], cell[1], cell[5] for i in [1, 2, 5, 6]: r_cell(state[i]) state[1], state[2], state[5], state[6] = state[5], state[1], state[6], state[2] return state def f(state): # 前面顺时针旋转一次 def f_cell(cell): # 前面顺时针旋转一次对应的每个块的面编码变化 cell[1], cell[2], cell[3], cell[4] = cell[4], cell[1], cell[2], cell[3] for i in [0, 1, 4, 5]: f_cell(state[i]) state[0], state[1], state[4], state[5] = state[4], state[0], state[5], state[1] return state def u_whole(state): # 上+下面顺时针旋转一次 def u_d_cell(cell): # 上+下面顺时针旋转一次对应的每个块的面编码变化 cell[4], cell[5], cell[2], cell[0] = cell[0], cell[4], cell[5], cell[2] for i in range(8): u_d_cell(state[i]) state[0], state[1], state[2], state[3] = state[1], state[2], state[3], state[0] state[4], state[5], state[6], state[7] = state[5], state[6], state[7], state[4] return state def r_whole(state): # 右+左面顺时针旋转一次 def r_l_cell(cell): # 右+左面顺时针旋转一次对应的每个块的面编码变化 cell[0], cell[1], cell[5], cell[3] = cell[3], cell[0], cell[1], cell[5] for i in range(8): r_l_cell(state[i]) state[1], state[2], state[5], state[6] = state[5], state[1], state[6], state[2] state[0], state[3], state[4], state[7] = state[4], state[0], state[7], state[3] return state def f_whole(state): # 前+后面顺时针旋转一次 def f_b_cell(cell): # 前+后面顺时针旋转一次对应的每个块的面编码变化 cell[1], cell[2], cell[3], cell[4] = cell[4], cell[1], cell[2], cell[3] for i in range(8): f_b_cell(state[i]) state[0], state[1], state[4], state[5] = state[4], state[0], state[5], state[1] state[3], state[2], state[7], state[6] = state[7], state[3], state[6], state[2] return state def try_add(state): for _ in range(4): state = u_whole(deepcopy(state)) for _ in range(4): state = r_whole(deepcopy(state)) for _ in range(4): state = f_whole(deepcopy(state)) if process_cube(state) in states: return states.add(process_cube(state)) queue.append(state) if __name__ == '__main__': cube = [['o', 'y', 'x', 'x', 'g', 'x'], ['o', 'y', 'g', 'x', 'x', 'x'], ['x', 'y', 'g', 'x', 'x', 'y'], ['x', 'y', 'x', 'x', 'g', 'y'], ['o', 'x', 'x', 'o', 'g', 'x'], ['o', 'x', 'g', 'o', 'x', 'x'], ['x', 'x', 'g', 'o', 'x', 'y'], ['x', 'x', 'x', 'o', 'g', 'y']] queue, states = deque(), set() queue.append(cube) states.add(process_cube(cube)) while queue: front = queue.popleft() u_state = u(deepcopy(front)) try_add(u_state) r_state = r(deepcopy(front)) try_add(r_state) f_state = f(deepcopy(front)) try_add(f_state) print(len(states)) 

Answer: 229878