URI Online Judge | 1100

Movimientos del Caballo

Autor Desconocido

Tiempo Límite: 1

Peter está haciendo una investigación sobre el Problema del Caballo Viajero (PCV) donde tienes que encontrar el recorrido cerrado más corto de movimientos del caballo que pase por cada casilla de un conjunto dado de n casillas exactamente una vez. Él cree que la parte más difícil del problema es determinar el menor número de movimientos del caballo entre dos cuadrados y que, una vez haya logrado eso, encontrar el recorrido sería fácil.

Por supuesto tú sabes que es al revés. Así que debes ofrecerle un programa que resuelva la parte "difícil".

Tu trabajo es escribir un programa que tome dos casillas a y b como entrada y determine el número de movimientos del caballo en la ruta más corta desde a hasta b.

Entrada

El archivo de entrada contendrá uno o más casos de prueba. Cada caso de prueba contiene dos casillas separadas por un espacio. Una casila es una cadena de caracteres que consiste en una letra (a-h) que representa la columna y un dígito (1-8) que representa la fila en el tablero. Como se muestra en la figura de arriba.

Salida

Para cada caso de prueba, imprime una línea que diga "To get from xx to yy takes n knight moves.". Donde xx es el origen, yy es el destino y n es la cantidad de pasos que se necesitan para ir desde xx hasta yy.

Ejemplo de Entrada Ejemplo de salida

e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6

To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.