1449：【例题2】魔板

时间限制: 1000 ms
内存限制: 65536 KB
提交数: 2550
通过数: 1405

题目描述

在成功地发明了魔方之后，拉比克先生发明了它的二维版本，称作魔板。这是一张有 $8$ 个大小相同的格子的魔板： 1 2 3 4 8 7 6 5

我们知道魔板的每一个方格都有一种颜色。这 $8$ 种颜色用前 $8$ 个正整数来表示。可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。对于上图的魔板状态，我们用序列 $(1, 2, 3, 4, 5, 6, 7, 8)$ 来表示。这是基本状态。

这里提供三种基本操作，分别用大写字母 “A”，“B”，“C” 来表示（可以通过这些操作改变魔板的状态）：

• “A”：交换上下两行；
• “B”：将最右边的一行插入最左边；
• “C”：魔板中央作顺时针旋转。

下面是对基本状态进行操作的示范： 8 7 6 5 4 1 2 3 1 7 2 4 A: 1 2 3 4 B: 5 8 7 6 C: 8 6 3 5

对于每种可能的状态，这三种基本操作都可以使用。

你要编程计算用最少的基本操作完成基本状态到特殊状态的转换，输出基本操作序列。

输入格式

只有一行，包括 $8$ 个整数，用空格分开（这些整数在范围 $1$ —— $8$ 之间），表示目标状态。

输出格式

第一行：包括一个整数，表示最短操作序列的长度。

第二行：在字典序中最早出现的操作序列，用字符串表示，除最后一行外，每行输出 $60$ 个字符。

输入输出样例

2 6 8 4 5 7 3 1

7 BCABCCB

提示

注意操作序列的字典序：在保证最短的前提下，输出字典序最小的操作序列。搜索时按照 A、B、C 的顺序进行扩展即可得到字典序最小的解。