Farmers and knight P56143
Given an n × m board that contains farmers, a knight and some obstacles, you have to find a shortest path form the knight to any farmer. Asume that farmers do not move, and that the knight can move to any of its eight adjacent cells which do not have an obstacle.
Input
Input consists of several cases, each starting with n and m, followed by n rows, each which m characters. A ‘K’ represents a knight, an ‘F’ is a farmer, an ‘X’ is an obstacle, and a ‘.’ is an empty cell. You can assume 3 ≤ n ≤ 1000, 3 ≤ m ≤ 1000, that the board has exactly one knight and at least one farmer, and that the first row, the last row, the first column, and the last column only have obstacles.
Output
For each board, print the minimum number of cells to go from the knight to any farmer, followed by the coordinates (numbered from 0) of the path. If there is more than one solution, print any of them. If there is no solution, print 0. Please have a look at the 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