The hungry knight P17866


Statement
 

pdf   zip

A knight is on a chess board. The knight can only move following the usual chess rules (that is, moving two units in one coordinate, and one unit in the other coordinate, for a total of up to eight possible movements), as long as the knight does not leave the board, nor it visits any forbidden cell. What is the minimum number of steps to reach a carrot?

Input

Input consists of several cases. Each case begins with the number of rows ff and the number of columns cc of the board, both between 3 and 200. Follow ff rows with cc characters each. A ‘p’ indicates a carrot, an ‘X’ indicates a forbidden cell, and a period indicates a free cell. Every case ends with the initial position (row and column) of the knight. The left-most cell of the first row is (1, 1). The initial cell is always free.

Output

For every case, if the knight can reach some carrot, print the minimum number of steps. Otherwise, print “no”.

Public test cases

  • Input

    3 3
...
..p
...
1 1

4 6
XXXXXX
X..XXX
XXXX.X
pX.XXX
2 3

3 4
XXXX
XXX.
XXXX
2 4

3 4
ppXX
p.pp
ppp.
3 4

    Output

    1
4
no
no
    • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python