Ordenant el puzzle P27048


Statement
 

pdf   zip

html

Considereu un puzzle consistent en un taulell n × m, on totes les caselles excepte una tenen un número diferent entre 1 i n*m − 1. L’únic moviment permès consisteix a desplaçar a la casella buida un número adjacent (horitzontalment o verticalment), cosa que fa que la casella buida “es mogui” a on estava el número. L’objectiu és deixar el puzzle ordenat de dalt a baix i d’esquerra a dreta, amb la casella buida abaix a la dreta.

Feu un programa que digui si un puzzle donat té solució o no. Si en té, cal dir quin és el mínim nombre de passos per resoldre’l.

Entrada

L’entrada consisteix en dos naturals estrictament positius (i petits) n i m, seguits de n files amb m naturals cadascuna. Cada número entre 0 i n*m − 1 apareix exactament un cop; el zero marca la casella inicialment buida.

Sortida

Escriviu el mínim nombre de passos per resoldre el puzzle, seguint el format dels exemples. Si no hi ha cap solució possible, escriviu "no te solucio".

Public test cases

  • Input

    3 5
 1  2  3  4  5
 6  7  8  9 10
11 12 13 14  0

    Output

    te solucio en 0 passos

  • Input

    1 6
1 2 3 4 0 5

    Output

    te solucio en 1 passos

  • Input

    2 3
1 0 5
4 3 2

    Output

    te solucio en 6 passos

  • Input

    2 2
1 3
2 0

    Output

    no te solucio

  • Input

    3 3
1 5 2
8 7 6
3 4 0

    Output

    te solucio en 16 passos
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions