题目描述

John 用他的一头母牛和 Don 先生交换了一头“骑士牛”。这头牛有一个独特的能力——在牧场中能像中国象棋中的马一样跑跳。当然，这头牛不能跳到岩石或树上，不过能跳到有牧草的地方。这儿有一个宽为 $X$，高为 $Y$ 的矩形牧场。“骑士牛”和其它牛一样喜欢干草。给你一张包含“骑士牛”出发地和树、岩石、灌木或其它障碍物及大包干草等位置信息的地图，确定“骑士牛”得到干草最少要跳几“跳”。地图中“骑士牛”出发地用 K 表示；障碍物用 * 表示，牧草用 . 表示，干草所在地用 H 表示。这儿有一个示例地图：

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

骑士牛得到干草的最少步骤在下图中用 $A,B,C \dots F$表示，最少要跳 $5$“跳”（其它的路径可能超过$5$“跳”）：

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

输入格式

第 $1$ 行: 两个空格隔开的整数: $X$ 和 $Y$

第 $2 \dots Y+1$ 行: 第 $Y-i+2$ 行包含 $X$ 个没有空格的字符（就像上面的地图一样）：表示第 $i$ 行的地图。

输出格式

第 $1$ 行: 一个单独的整数表示最少的得到干草的“跳”数。所有的数据都能得到干草。

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

5

数据范围

$1 \leq X \leq 150$

$1 \leq Y \leq 150$