Camelot
Secoli fa, Re Artù e i Cavalieri della Tavola Rotonda si incontravano
ogni Capodanno per festeggiare la loro amicizia. Nel ricordo di questi
eventi, consideriamo un gioco da scacchiera per un giocatore, in cui un
re e diversi cavalli sono posizionati a caso su caselle distinte. La scacchiera
è un matrice di 8x8 caselle.
Figura 1. Una scacchiera
Il re può muoversi in qualunque casella adiacente da
a , come viene mostrato
nella figura 2, purché non caschi fuori dalla scacchiera.
Figura 2. Tutte le possibili mosse del re
Un cavallo può saltare da
a , come viene mostrato
nella figura 3, purché non caschi fuori dalla scacchiera.
Figura 3. Tutte le possibili mosse di un cavallo
Durante il gioco, il giocatore può posizionare più di
un pezzo nella stessa casella. Si assume che le caselle della scacchiera
siano abbastanza grandi da far sì che un pezzo non sia mai di ostacolo
per un altro.
L'obiettivo del giocatore è di spostare i pezzi in modo da radunarli
tutti nella stessa casella nel minimo numero possibile di mosse. Per ottenere
questo risultato, il giocatore deve spostare i pezzi come descritto in
precedenza. Inoltre, se il re e uno o più cavalli sono nella stessa
casella, il giocatore può decidere di muovere da lì in poi
il re e uno dei cavalli insieme, come un singolo cavallo, fino al punto
di raduno finale. Lo spostamento del cavallo e del re insieme conta come
una sola mossa.
Il problema
Scrivete un programma che calcoli il numero minimo di mosse che il giocatore
deve effettuare per radunare tutti i pezzi in una casella.
Dati in input
Il file CAMELOT.IN contiene la configurazione iniziale della scacchiera,
codificata sotto forma di stringa di caratteri. La stringa contiene una
sequenza di fino a 64 posizioni distinte della scacchiera, dove la prima
posizione è quella del re e le rimanenti quelle dei cavalli. Ogni
posizione è data da una coppia lettera/cifra. Le lettere indicano
le coordinate orizzontali (ascisse) della schiacchiera, mentre le cifre
quelle verticali (ordinate).
Esempio di input
D4A3A8H1H8
Il re è posizionato in D4. Ci sono quattro cavalli, posizionati
in A3, A8, H1 e H8.
Dati in output
Il file CAMELOT.OUT deve contenere una sola riga con un intero
che indica il minimo numero di mosse che il giocatore deve effettuare per
radunare tutti i pezzi.
Esempio di output
10
Vincoli
0 <= numero di cavalli <= 63