Farmers and knight P56143


Statement
 

pdf   zip

thehtml

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.

Public test cases
  • 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
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Original language
    Catalan
    Other languages
    Catalan Spanish
    Official solutions
    C++
    User solutions
    C++