Pagesos i cavaller P56143
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.
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