Pagesos i cavaller P56143

Donat un tauler $n \times 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 \le n \le 1000$, $3 \le m \le 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.