IOI'94 - Day 2 - Problem 1: The Clocks

|-------|    |-------|    |-------|    
|       |    |       |    |   |   |    
|---O   |    |---O   |    |   O   |          
|       |    |       |    |       |           
|-------|    |-------|    |-------|    
    A            B            C

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
|-------|    |-------|    |-------|
    D            E            F

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|  (Figure 1)
    G            H            I

---

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.

Input Data

Read nine numbers from the INPUT.TXT file. These
numbers give the start positions of the dials. 0=12 o'clock, 1=3 o'clock, 2=6
o'clock, 3=9 o'clock. The example in figure 1 gives the following input data
file:

3 3 0
2 2 2 
2 1 2

Output Data

Write to the OUTPUT.TXT file a shortest sequence
of moves (numbers), which returns all the dials to 12 o'clock. In case there are
many solutions, only one is required. In our example the OUTPUT.TXT
file could look as follows:

5849

---

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

---

Example of Method

Each number represents a time accoring to following
table:

0 = 12 o'clock
1 = 3 o'clock
2 = 6 o'clock 
3 = 9 o'clock

3 3 0         3 0 0         3 0 0          0 0 0         0 0 0 
2 2 2   5->   3 3 3   8->   3 3 3   4 ->   0 3 3   9->   0 0 0 
2 1 2         2 2 2         3 3 3          0 3 3         0 0 0