El cavall saltador P43694


Statement
 

pdf   zip

thehtml

Teniu un taulell n × n, on cada posició pot estar permesa o prohibida. Donada la posició inicial d’un cavall, cal determinar si és possible que el cavall passi exactament un cop per cada posició permesa, fent els salts dels escacs (és a dir, incrementant o decrementant una de les dimensions en una unitat, i l’altra dimensió en dues unitats).

Entrada

L’entrada consisteix en un natural 3 ≤ n < 10, seguit de n línies amb n caràcters cadascuna: un ’*’ indica una posició prohibida, un punt indica una posició permesa. Finalment, un parell d’enters f i c entre 1 i n indiquen la fila inicial i la columna inicial del cavall; la cantonada de dalt a l’esquerra és (1, 1). La posició inicial del cavall mai no estarà prohibida.

Sortida

Escriviu un camí del cavall per totes les posicions permeses seguint el format dels exemples. Fixeu-vos que cada posició per la qual passa el cavall es marca amb dos dígits (si cal, omplint amb un zero), començant en 01 i incrementalment.

Si hi ha més d’un camí possible, escolliu-ne qualsevol. Si no hi ha cap solució possible, cal escriure "no sol".

Public test cases
  • Input

    4
    ....
    ....
    ....
    ...*
    4 1
    

    Output

    10 15 06 03
    07 04 09 12
    14 11 02 05
    01 08 13 **
    
  • Input

    5
    ...*.
    .*...
    ....*
    .*...
    *..*.
    3 2
    

    Output

    02 13 18 ** 04
    19 ** 03 08 17
    14 01 12 05 **
    11 ** 07 16 09
    ** 15 10 ** 06
    
  • Input

    3
    ...
    ...
    ...
    1 1
    

    Output

    no sol
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++