Pagesos i cavaller P56143


Statement
 

pdf   zip

thehtml

Donat un tauler n × m que conté pagesos, un cavaller i alguns obstacles, trobeu un camí mínim del cavaller fins a qualsevol pagès. Suposeu que els pagesos estan immòvils, i que el cavaller es pot moure a qualsevol de les vuit caselles adjacents que no tinguin un obstacle.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n i m, seguides de n files, cadascuna amb m ‍caràcters. Una ‘K’ indica un cavaller, una ‘F’ un pagès, una ‘X’ un obstacle, i un ‘.’ una casella buida. Podeu suposar 3 ≤ n ≤ 1000, 3 ≤ m ≤ 1000, que el tauler té exactament un cavaller i almenys un pagès, i que la primera fila, l’última fila, la primera columna i l’última columna només tenen obstacles.

Sortida

Per a cada tauler, escriviu el nombre mínim de caselles per anar del cavaller a qualsevol pagès, seguit de les coordenades (numerades des de 0) del camí. Si hi ha més d’una solució, escriviu-ne una qualsevol. Si no n’hi ha cap, escriviu 0. Fixeu-vos en el format.

Public test cases
  • Input

    3 5
    XXXXX
    XK.FX
    XXXXX
    
    3 5
    XXXXX
    XKXFX
    XXXXX
    
    8 9
    XXXXXXXXX
    XF.....FX
    X.XX.X..X
    X...K...X
    X.......X
    X.......X
    X...F...X
    XXXXXXXXX
    

    Output

    3  1 1  1 2  1 3
    0
    4  3 4  3 5  2 6  1 7
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English Spanish
    Official solutions
    C++
    User solutions
    C++