编程介的小学生 2017-03-26 16:04 采纳率: 20.5%
浏览 942
已采纳

Cubic Eight-Puzzle

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.

Coloring of Cubes: All the cubes area colored in the same way as shown in Figure 1. The opposite faces have the same color.

Figure 1: Coloring of a cube

Initial Board State: Eight cubes are placed on the 3 �� 3 board leaving one empty square. All the cubes have the same orientation as shown in Figure 2. As shown in the figure, squares on the board are given x and y coordinates, (1, 1), (1, 2), ��, and (3, 3). The position of the initially empty square may vary.

Figure 2: Initial board state

Rolling Cubes: At each step, we can choose one of the cubes adjacent to the empty square and roll it into the empty square, leaving the original position empty. Figure 3 shows an example.

Figure 3: Rolling a cube

Goal: The goal of this puzzle is to arrange the cubes so that their top faces form the specified color pattern by a number of cube rolling steps described above.

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.

Input

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.

Output

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.

Sample 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
Sample Output

0
3
13
23
29
30
-1
-1

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-04-05 15:36
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 C#调用python代码(python带有库)
  • ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能
  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
  • ¥50 NT4.0系统 STOP:0X0000007B