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.