Campesinos y caballero P56143
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.
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