1386. 北京2008的挂钟

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

        [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

输入数据

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

输出数据

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

样例输入

复制
3 3 0
2 2 2
2 1 2
 · · \n
 · · \n
 · · \n

样例输出

复制
4 5 8 9
 · · · \n

样例说明

[b]Description[/b]&nbsp

&nbsp &nbsp &nbsp &nbsp [IMG]http://www.Vijos.cn/ProblemImg/P1016.gif[/IMG]
(Figure&nbsp 1)

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

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

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

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

提交

请先 登录

Source

Vivian  Snow IOI  1994  The  Clocks,  From  PKU  1166

© 2024 FAQs Contact About