题目描述

旋转游戏使用一个“#”形棋盘，可放置24个方块（见图1）。方块标记为1、2、3，每种恰好8个。

初始时，方块随机放置在棋盘上。你的任务是移动方块，使中心正方形的8个方块标记相同。唯一有效移动是旋转四条线中的一条，每条线包含7个方块——将线中的6个方块向头部移动一位，头部方块移至线的末尾。8种可能的移动标记为A到H。图1展示了从某初始状态连续执行A和C移动的过程。

输入格式

• 输入不超过30个测试用例，每个用例一行包含24个数字，表示初始方块标记。
• 按从上到下的行列出方块，每行从左到右排列，数字用空格分隔。样例输入的第一个用例对应图1的初始状态。
• 用例间无空行，最后一个用例后有一行单独的0结束输入。

输出格式

• 对每个用例，输出两行：
  第一行是到达目标状态的所有移动步骤（A-H），无空格。若无需移动，输出No moves needed。
  第二行是中心正方形的标记。若有多个解，选移动步数最少的；步数相同则选字典序最小的。

输入样例 1

1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
0

输出样例 1

AC
2
DDHH
2

来源

上海2004年相关问题