Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: Problem 3: Magic Squares
发信站: 哈工大紫丁香 (2002年03月29日13:55:44 星期五), 站内信件

Problem 3: Magic Squares
Following the success of the magic cube, Mr. Rubik invented its planar versi
on, called magic squares. This is a sheet composed of 8 equal-sized squares 
(see Figure 3).
　
----------------------------------------------------------------------------
----
1 2 3 4
8 7 6 5
Figure 3: Initial configuration
----------------------------------------------------------------------------
----
In this task we consider the version where each square has a different colou
r. Colours are denoted by the first 8 positive integers (see Figure 3). A sh
eet configuration is given by the sequence of colours obtained by reading th
e colours of the squares starting at the upper left corner and going in cloc
kwise direction. For instance, the configuration of Figure 3 is given by the
 sequence (1,2,3,4,5,6,7,8). This configuration is the initial configuration
.
Three basic transformations, identified by the letters 'A', 'B' and 'C', can
 be applied to a sheet:
'A': exchange the top and bottom row,
'B': single right circular shifting of the rectangle,
'C': single clockwise rotation of the middle four squares.
All configurations are available using the three basic transformations.
　
----------------------------------------------------------------------------
----
A: 1 2 3 4
8 7 6 5
1 2 3 4
8 7 6 5
 B: 1 2 3 4
4 1 2 3
5 8 7 6
8 7 6 5
 C: 1 2 3 4
1 7 2 4
8 6 3 5
8 7 6 5
Figure 4: Basic transformations
----------------------------------------------------------------------------
----
The effects of the basic transformations are described in Figure 4. Numbers 
outside the squares denote square positions. If a square in position p conta
ins number i, it means that after applying the transformation, the square wh
ose position was i before the transformation moves to position p.
You are to write a program that computes a sequence of basic transformations
 that transforms the initial configuration of Figure 3 to a specific target 
configuration (Subtask A). Two extra points will be given for the solution i
f the length of the transformation sequence does not exceed 300 (Subtask B).

　
Input Data
The file INPUT.TXT contains 8 positive integers in the first line, the descr
iption of the target configuration.
　
　
Output Data
On the first line of file OUTPUT.TXT your program must write the length L of
 the transformation sequence. On the following L lines it must write the seq
uence of identifiers of basic transformations, one letter in the first posit
ion of each line.
　
Tool
MTOOL.EXE is a program in the task directory that lets you play with the mag
ic squares. By executing "mtool input.txt output.txt" you can experiment wit
h the target configuration and the sequence of transformations.
　
Example Input and Output
----------------------------------------------------------------------------
----
INPUT.TXT               OUTPUT.TXT
2 6 8 4 5 7 3 1         7
                        B
                        C
                        A
                        B
                        C
                        C
                        B
----------------------------------------------------------------------------
----
Figure 5: Example Input and Output
　

--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]