2 人解决，4 人已尝试。
2 份提交通过，共有 11 份提交。
9.2 EMB 奖励。
1715. Cubic Eight-Puzzle
单点时限: 10.0 sec
内存限制: 256 MB
Let’s play a puzzle using eight cubes placed on a 3 × 3 board leaving one empty square.
Faces of cubes are painted with three colors. As a puzzle step, you can roll one of the cubes to a adjacent empty square. Your goal is to make the specified color pattern visible from above by a number of such steps.
The rules of this puzzle are as follows.
Your task is to write a program that finds the minimum number of steps required to make the specified color pattern from the given initial state.
输入格式
The input is a sequence of datasets. The end of the input is indicated by a line containing two zeros separated by a space. The number of datasets is less than 16. Each dataset is formatted as follows.
x y
F11 F21 F31
F12 F22 F32
F13 F23 F33
The first line contains two integers x and y separated by a space, indicating the position (x, y) of the initially empty square. The values of x and y are 1, 2, or 3.
The following three lines specify the color pattern to make. Each line contains three characters F1j, F2j, and F3j, separated by a space. Character Fij indicates the top color of the cube, if any, at the position (i, j) as follows:
B: Blue,
W: White,
R: Red,
E: the square is Empty.
There is exactly one ‘E’ character in each dataset.
输出格式
For each dataset, output the minimum number of steps to achieve the goal, when the goal can be reached within 30 steps. Otherwise, output “-1” for the dataset.
样例
Input
1 2 W W W E W W W W W 2 1 R B W R W W E W W 3 3 W B W B R E R B R 3 3 B W R B W R B E R 2 1 B B B B R B B R E 1 1 R R R W W W R R E 2 1 R R R B W B R R E 3 2 R R R W E W R R R 0 0
Output
0 3 13 23 29 30 -1 -1
题目标签