Knight's Grass Hunt

The problem is as follows: A magical knight (represented by K) is roaming on a grid much like a cow that loves grass. The grid contains obstacles (marked as *), empty cells (marked as .), and a patch of grass (marked as H). The knight can jump in the pattern of a chess knight. That is, from any cell (x, y), he can move to any of the eight positions:

$$\{(x+2,y+1), (x+1,y+2), (x-1,y+2), (x-2,y+1), (x-2,y-1), (x-1,y-2), (x+1,y-2), (x+2,y-1)\}$$

Note that the knight can jump over obstacles, but he cannot land on a cell containing an obstacle (*). Your task is to determine the minimum number of knight jumps required for the knight to reach the grass (H). If it is impossible to reach the grass, output -1.

Example:

11 10
..........
....*.....
..........
...*.*....
.......*..
..*..*...H
*.........
...*..*...
.K........
...*.....*
..*....*..

In the sample above, one possible path requires 5 jumps.

inputFormat

The input begins with two integers n and m representing the number of rows and columns respectively. Following this, there are n lines, each containing a string of m characters. Each character is one of the following:

• K: the starting position of the knight.
• H: the location of the grass.
• *: an obstacle.
• .: an empty cell.

It is guaranteed that there is exactly one K and one H in the grid.

outputFormat

Output a single integer representing the minimum number of knight moves required to reach the grass. If the grass cannot be reached, output -1.

sample

3 3
K..
.*.
.H.

1