Algorithm 版 (精华区)

发信人: sino (仿佛永远分离 却又终身相依), 信区: Algorithm
标  题: Contest Part I Problem 4
发信站: 哈工大紫丁香 (2002年08月16日09:19:42 星期五), 站内信件

魔板(30分)
在魔方风靡全球之后,Rubik先生发明它的简化版—魔板. 魔板由8个同样大小的方
块组成,每个方块的颜色均不相同,本题中以数字1-8分别表示,可能出现在魔板的任
一位置,任一时刻魔板的状态可以用方块的数字序列表示:从魔板的左上角开始,按
顺时针方向依次写下各方块的代号,得到的数字序列即可表示此时的魔板的状态.例
如,序列(1,2,3,4,5,6,7,8)表示下面的魔板的状态
1   2   3   4
5   6   7   8
这也就是题中魔板的初始状态.对于魔板,可以施加三种不同的操作,分别以A,B,C标
示,具体操作方法如下:
A.  上下行互换
B.  每一行同时循环右移一格
C.  中间4个方块顺时针旋转一格
应用这三种基本操作,可以由任一状态达到任意另一状态,下面描述了应用这三种操
作之后魔板的状态变化,

8   7   6   5
1   2   3   4
A
4   1   2   3
5   8   7   6
B
1   7   2   4
8   6   3   5
C
请编程序,对于输入的一个目标状态,寻找一种操作的序列,使得从初始状态开始,经
过此操作序列后使该魔板变为目标状态
输入数据:
    文件名input.txt,第1行包含8个以一个空格分隔的正整数,表示目标状态
输出数据:
    文件名output.txt,在第一行输出你的程序寻找到的操作序列的步数L,随后L行是
相应的操作序列,每行的行首写一个字符,代表相应的操作.
示例:
Input.txt
2 6 8 4 5 7 3 1

Output.txt
7BCABCCB

--
SecureNetTerm can be dowloaded to all countries except
Cuba, Iran, Iraq, Libya, North Korea, Sudan and Syria.

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.226.228]