The Chivalrous Cow

Farmer John traded one of his cows for a cow called "The Knight." This cow jumps around the pasture exactly like a knight on a chessboard: each jump moves two squares in one direction and one square in the perpendicular direction (an "L" shape). The Knight cannot land on an obstacle, but she can freely hop across the pasture, which is divided into an $X \times Y$ grid of squares ($1 \le X \le 150$, $1 \le Y \le 150$).

The Knight loves hay. Given a map showing her starting square, the obstacles, and the hay bale, determine the minimum number of jumps she needs to reach the hay. On the map, the Knight's starting square is marked K, every obstacle is marked *, and the hay bale is marked H; empty squares are ..

A typical map looks like this (row and column numbers are shown only as a guide):

11 | . . . . . . . . . .
10 | . . . . * . . . . .
 9 | . . . . . . . . . .
 8 | . . . * . * . . . .
 7 | . . . . . . . * . .
 6 | . . * . . * . . . H
 5 | * . . . . . . . . .
 4 | . . . * . . . * . .
 3 | . K . . . . . . . .
 2 | . . . * . . . . . *
 1 | . . * . . . . * . .
 0 ----------------------
                       1
   0 1 2 3 4 5 6 7 8 9 0

In this map, the Knight can reach the hay bale H from her starting square K in as few as 5 jumps (other routes of length 5 may also exist). It is guaranteed that the hay bale can always be reached.

• The first line contains two space-separated integers $X$ and $Y$.
• Each of the next $Y$ lines contains exactly $X$ characters with no spaces, giving the map one row at a time from the top row to the bottom row. Each character is . (empty), * (obstacle), K (the Knight's start), or H (the hay bale). There is exactly one K and exactly one H.

• Print a single integer: the minimum number of jumps the Knight needs to reach the hay bale. It is always possible to reach the hay bale.