N-Puzzle P71846


Statement
 

pdf   zip

thehtml

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:

||

ABCD
EFGH
IJKL
MNO.

||

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.

Public test cases
  • Input

    ABCD
    EFGH
    IJKL
    M.NO
    

    Output

    2
    
  • Input

    .BCD
    EAGH
    IJFL
    MNOK
    

    Output

    6
    
  • Information
    Author
    COCI06/07
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++