魔方(Rubik’s Cube)问题

Description:

3×3×3魔方的构造如图所示。图中英文字母U，L，F，R，B，D 分别表示魔方的6 个面中的上面，左面，前面，右面，后面，底面。魔方的每个面都可以绕其中轴旋转。给定魔方的初始状态，可以经过若干次旋转将魔方变换成每个面都只有一种颜色的状态。绕中轴将一个面旋转90 度算作一次旋转。试设计一个算法计算出从初始状态到目标状态（每个面都只有一种颜色的状态）所需的最少旋转次数。

设计一个算法，对于给定的3×3×3魔方的初始状态，计算从初始状态到目标状态（每个面都只有一种颜色的状态）所需的最少旋转次数。

Input:

3×3×3魔方目标状态的每个面都有一种颜色，分别用大写英文字母W，O，G，R，Y，B来表示。将6个面展开并编号如下图所示。文件将给定魔方的初始状态的6 个面，按照其编号依次排列，共有18 行，每行有3 个表示方块颜色的大写英文字母。

Output:

文件的第一行是最少旋转次数；接下来是最优旋转序列。用表示各面大写英文字母表示每个面的顺时针旋转；表示各面大写英文字母紧接一个“-”表示每个面的逆时针旋转。如果不存在满足要求的旋转序列则输出“No Solution!”。

Sample Input:

G W W
G W W
G R R
W W W
O O O
O O O
O G G
B G G
B G G
B R R
B R R
B R R
Y Y R
Y Y W
Y Y W
Y O O
Y B B
Y B B

Sample Output:

2
L F

Note:

undefined

本题由旧版NOJ导入，来源：算法设计与实验题解