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:

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

Idea dell'algoritmo

Si può notare che ciascuna mossa può essere effettuata al più 3 volte, poiché quattro esecuzioni della stessa mossa non hanno alcun effetto, riportando gli orologi coinvolti alla posizione iniziale. Inoltre, l'ordine delle mosse non è importante.
La soluzione consiste nell'effettuare una ricerca in ampiezza (breadth-first) sullo spazio delle soluzioni: notate che, essendo il numero di orologi noto a priori, non è necessario utilizzare una coda, ma basta utilizzare un insieme di cicli for annidati.