1016. 北京2008的挂钟

时间限制 1000 ms
内存限制 128 MB

题目描述

  

  在2008北京奥运会雄伟的主会场的墙上,挂着如上图所示的3*3的九个挂钟(一开始指针即时针指向的位置请根据输入数据调整)。然而此次奥运会给与了大家一个机会,去用最少的移动操作改变上面的挂钟的时间全部为12点正(我们只考虑时针)。然而每一次操作并不是任意的,我们必须按照下面给出的列表对于挂钟进行改变。每一次操作我们给而且必须给指定的操作挂钟进行,每一个挂钟顺时针转动90度。列表如下:

  操作 指定的操作挂钟
   1     ABDE
   2     ABC
   3     BCEF
   4     ADG
   5     BDEFH
   6     CFI
   7     DEGH
   8     GHI
   9     EFHI

输入数据

  你的程序按照标准的 $3*3$ 格式读入,一共 $9$ 个 $0-3$ 的数。 $0$ 代表 $12$ 点 $,1$ 代表 $3$ 点 $,2$ 代表 $6$ 点 $,3$ 代表 $9$ 点。
  Your program is to read from standard input. Nine numbers give the start positions of the dials. 0=12 o'clock, 1=3 o'clock, 2=6 o'clock, 3=9 o'clock.

输出数据

  你的程序需要写出标准的输出。输出一个最短的能够使所有挂钟指向 $12$ 点的移动操作序列,中间以空格隔开,最后有空格,加回车。这一条最短操作需要是所有最短操作中最小的,也就是说选择最小的第一个操作数,如果第一个操作数相等,那么选择最小的第二个操作数……以此类推。值得肯定的是,这一条操作序列是唯一的。
  Your program is to write to standard output. Output a shortest sorted sequence of moves (numbers), which returns all the dials to 12 o'clock. You are convinced that the answer is unique.

样例输入

3 3 0
2 2 2
2 1 2

样例输出

4 5 8 9

样例说明

Description

  
(Figure 1)

There are nine clocks in a 3*3 array (figure 1). The goal is to return all the dials to 12 o'clock with as few moves as possible. There are nine different allowed ways to turn the dials on the clocks. Each such way is called a move. Select for each move a number 1 to 9. That number will turn the dials 90' (degrees) clockwise on those clocks which are affected according to figure 2 below.

Move Affected clocks

1     ABDE
2     ABC
3     BCEF
4     ADG
5     BDEFH
6     CFI
7     DEGH
8     GHI
9     EFHI  
(Figure 2)

Input
Your program is to read from standard input. Nine numbers give the start positions of the dials. 0=12 o'clock, 1=3 o'clock, 2=6 o'clock, 3=9 o'clock.

Output
Your program is to write to standard output. Output a shortest sorted sequence of moves (numbers), which returns all the dials to 12 o'clock. You are convinced that the answer is unique.

题目信息

未提交
未通过无法查看
未通过无法查看