N-Puzzle P71846

Un N-puzzle es un tipo de puzzle que tiene muchas variantes distintas. En este problema consideraremos el 15-puzzle. Consiste en un tablero 4 por 4 con fichas que pueden deslizarse, y donde una ficha está ausente. Los cuadrados se etiquetan con letras mayúsculas de la ’A’ a la ’O’. Resolver el puzzle consiste en colocar cada ficha en la siguiente posición final:

||

||

La “dispersión” del puzzle es “la suma de las distancias entre la posición actual y la posición final de cada ficha”. La distancia entre dos posiciones es su distancia de Manhattan (o sea, la suma de los valores absolutos de las diferencias entre las dos columnas y las dos filas).

Escribe un programa que calcule la “dispersión” de un puzzle dado.

Entrada

Cuatro líneas con cuatro caracteres cada una, representando el estado actual del puzzle.

Salida

Escribe una línea con la dispersión del puzzle.