Campesinos y caballero P56143


Statement
 

pdf   zip

thehtml

Dado un tablero n × m que contiene campesinos, un caballero y algunos obstáculos, encontrad un camino mínimo del caballero hasta cualquier campesino. Suponed que los campesinos no se mueven, y que el caballero se puede mover a cualesquiera de las ocho casillas adyacentes que no tengan un obstáculo.

Entrada

La entrada consiste en diversos casos, cada uno con n y m, seguidas de n filas, cada una con m ‍caracteres. Una ‘K’ indica un caballero, una ‘F’ un campesino, una ‘X’ un obstáculo, y un ‍‘.’ una casilla vacía. Podéis suponer 3 ≤ n ≤ 1000, 3 ≤ m ≤ 1000, que el tablero tiene exactamente un caballero y al menos un campesino, y que la primera fila, la última fila, la primera columna y la última columna sólo tienen obstáculos.

Salida

Para cada tablero, escribid el número mínimo de casillas para ir del caballero a cualquier campesino, seguido de las coordenades (numeradas desde 0) del camino. Si hay más de una solución, escribid cualquiera de ellas. Si no hay ninguna, escribid 0. Fijaos en el formato.

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
    Spanish
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan English
    Official solutions
    C++
    User solutions
    C++