IOI'94 - Giorno 2 - Problema 1: Gli orologi

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

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

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


Ci sono nove orologi in una matrice 3x3 (figura 1). L'obiettivo è fare in modo che tutti gli orologi segnino le 12 con il minor numero di mosse possibili. Ci sono nove diversi modi di spostare le lancette degli orologi: ognuno di essi viene chiamato mossa. Indichiamo le mosse con un numero da 1 a 9: quella mossa corrisponderà alla rotazione di 90 gradi in senso orario di alcuni degli orologi, secondo lo schema specificato sotto (figura 2).

Dati di input

Il file INPUT.TXT contiene nove numeri. Questi numeri danno le posizioni iniziali delle lancette: 0=ore 12, 1=ore 3, 2=ore 6, 3=ore 9. L'esempio in figura 1 corrisponde al seguente contenuto del file:
3 3 0
2 2 2 
2 1 2

Dati di output

I risultati vanno scritti sul file OUTPUT.TXT come la più breve sequenza di mosse (numeri), che riportano tutti gli orologi alle 12. Se ci sono più soluzioni, se ne deve comunque presentare una sola. Nel nostro esempio il file OUTPUT.TXT potrebbe essere come segue:
5849

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

Esempio di metodo

Ogni numero rappresenta un orario, secondo lo schema seguente:
0 = ore 12 
1 = ore 3 
2 = ore 6 
3 = ore 9
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