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
Figura 1. Una scacchiera

Il re può muoversi in qualunque casella adiacente da PartenzaArrivo, come viene mostrato nella figura 2, purché non caschi fuori dalla scacchiera.

Figura 2. Tutte le possibili mosse del re
Figura 2. Tutte le possibili mosse del re

Un cavallo può saltare da PartenzaArrivo, come viene mostrato nella figura 3, purché non caschi fuori dalla scacchiera.

Figura 3. Tutte le possibili mosse di un cavallo
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