Background

Farmer John has many cows, and he wants to trade one of them that Don calls The Knight. This cow has a unique superpower: it can jump around the farm like a knight (the same move as the knight in chess). Although this magical cow cannot jump onto trees or rocks, it can jump freely on the pasture, which we represent using an $x,y$ coordinate grid.

Problem Description

Like other cows, this magical cow loves to eat grass. You are given a map that marks The Knight’s starting position, as well as the positions of trees, bushes, rocks, and other obstacles; in addition, there is also a bale of hay. Your task is to determine the minimum number of jumps The Knight needs in order to reach the hay. The Knight’s position is marked with K, obstacles are marked with *, and the hay is marked with H.

Here is an example map:

             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 

The Knight can follow the path $A,B,C,D\dots$ shown below to reach the hay in $5$ jumps (it is possible that other routes also have length $5$):

             11 | . . . . . . . . . .
             10 | . . . . * . . . . .
              9 | . . . . . . . . . .
              8 | . . . * . * . . . .
              7 | . . . . . . . * . .
              6 | . . * . . * . . . F<
              5 | * . B . . . . . . .
              4 | . . . * C . . * E .
              3 | .>A . . . . D . . .
              2 | . . . * . . . . . *
              1 | . . * . . . . * . .
              0 ----------------------
                                    1
                0 1 2 3 4 5 6 7 8 9 0
                ```

## Input Format

The first line contains two integers, representing the number of columns ($\le 150$) and the number of rows ($\le 150$) of the farm.

The second line to the end: the map described above.

## Output Format

Output one integer, the minimum number of jumps.


```input1
10 11
..........
....*.....
..........
...*.*....
.......*..
..*..*...H
*.........
...*...*..
.K........
...*.....*
..*....*..

5

Hint

Hint: Problems like this can be solved using a simple first-in-first-out table (queue).

Translated by ChatGPT 5