拨钟问题

题目描述

有9个钟，排成一个3*3的矩阵。

现在需要用最少的移动，将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如下表所示，每个移动会将若干个时钟的指针沿顺时针方向拨动90度。

移动方法       受影响的时钟

1             ABDE

2             ABC

3             BCEF

4             ADG

5             BDEFH

6             CFI

7             DEGH

8             GHI

9             EFHI

输入

9个整数，表示各时钟指针的起始位置，相邻两个整数之间用单个空格隔开。其中，0=12点，1=3点，2=6点，3=9点。

输出

单独的一行包括一个用空格分开的将所有指针指向 12 点的最短移动顺序的列表。

如果有多种方案，输出那种使其连接起来的数字最小的方案。(举例来说 5 2 4 6 < 9 3 1 1)。

样例输入

3 3 0

2 2 2

2 1 2

样例输出

4 5 8 9