El cavall saltador P43694


Statement
 

pdf   zip

html

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++