Knight Moves

Interview

Time limit1sMemory limit128 MB

Summary

Find the fewest knight moves from K to X on a grid with blocked squares, or output -1 when unreachable.

Level: Easy3 of 10
Topics: BFS, Matrix
Solved: No attempts yet

Problem

In chess a knight moves two squares in one direction and then one square in a perpendicular direction. A knight jumps, so only the destination square has to be free; the squares it passes over may be occupied. In the diagram below the knight can move to any of the squares marked X.

You are given a grid, a starting square and a destination square. Find the least number of moves the knight needs to get from the start to the destination. Some squares of the grid may be blocked, and the knight cannot move onto them.

Input

The input consists of a single test case. The first line contains two integers $n$ and $m$ ( $2 \le n, m \le 100$ ), the height and the width of the grid. Each of the next $n$ lines contains $m$ characters describing the grid. The grid contains only . (an open square), # (a blocked square), K (the square the knight starts on) and X (the square the knight has to reach). There is exactly one K and exactly one X.

Output

Print a single line with one integer, the minimum number of moves the knight needs to reach the destination, or -1 if it cannot reach it. Print no spaces.

Examples2

Example 1
Input
```
5 4
K...
....
.#..
.#..
...X
```
Expected output
```
5
```
Example 2
Input
```
3 3
K..
.X.
...
```
Expected output
```
-1
```