Preparing NOJ

2×2×2魔方问题

1000ms 65536K

Description:

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

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

Input:

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

Output:

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

Sample Input:

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

Sample Output:

2
R U

Note:

undefined

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

Info

NOJ

Provider NOJ

Code NOJ1296

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet