问题 2092. -- 北京2008的挂钟

2092: 北京2008的挂钟

时间限制: 0 Sec  内存限制: 128 MB
提交: 0  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

        [IMG]http://www.Vijos.cn/ProblemImg/P1016.gif[/IMG]

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

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

输入 [bjdgz.in]

        你的程序按照标准的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.

输出 [bjdgz.out]

        你的程序需要写出标准的输出。输出一个最短的能够使所有挂钟指向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

提示

[b]Description[/b] 

        [IMG]http://www.Vijos.cn/ProblemImg/P1016.gif[/IMG]
(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)

[b]Input[/b] 
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.

[b]Output[/b] 
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.

标签

通过初赛 搜索 搜索与剪枝 IOI1994 VIJOS

[上一题][提交][讨论版][状态][下一题]