骑士牛

题目描述

农民 John 有很多牛，他想交易其中一头被 Don 称为 The Knight 的牛。

这头牛有一个独一无二的超能力，在农场里像国际象棋中的骑士一样地跳（就是我们熟悉的象棋中马的走法）。

虽然这头神奇的牛不能跳到树上和石头上，但是它可以在牧场上随意跳，我们把牧场用一个 $x, y$ 的坐标图来表示。

这头神奇的牛像其它牛一样喜欢吃草，给你一张地图，上面标注了 The Knight 的开始位置，树、灌木、石头以及其它障碍的位置，除此之外还有一捆草。

现在你的任务是，确定 The Knight 要想吃到草，至少需要跳多少次。

地图标记

• K 标记 The Knight 的开始位置
• * 标记障碍的位置（不能跳到这些格子）
• H 标记草的位置
• . 标记可通行的草地

骑士移动规则

The Knight 按照国际象棋中骑士的走法移动，即 "L" 形移动：

• 先走 2 格直线，再走 1 格直角
• 或先走 1 格直线，再走 2 格直角

具体来说，从当前位置 $(x, y)$ 可以跳到以下 8 个位置之一：

1. $(x+2, y+1)$
2. $(x+2, y-1)$
3. $(x-2, y+1)$
4. $(x-2, y-1)$
5. $(x+1, y+2)$
6. $(x+1, y-2)$
7. $(x-1, y+2)$
8. $(x-1, y-2)$

输入格式

第 1 行：两个数，表示农场的列数 C 和行数 R。

第 2..R+1 行：每行一个由 C 个字符组成的字符串，共同描绘出牧场地图。

注意： 输入的行数是 R 行，每行有 C 个字符。

输出格式

一个整数，表示跳跃的最小次数。

数据范围

$1 \le R, C \le 150$

输入样例

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

输出样例

5

样例解释

地图尺寸：$C = 10$（列数），$R = 11$（行数）

地图（11行10列）：

第1行（最上面一行，对应y=10或11，取决于坐标系）：..........
第2行：....*.....
第3行：..........
第4行：...*.*....
第5行：.......*..
第6行：..*..*...H
第7行：*.........
第8行：...*...*..
第9行：.K........
第10行：...*.....*
第11行（最下面一行，对应y=0或1）：..*....*..

地图中：

• K 位于第9行第2列（从0开始计数的话）
• H 位于第6行第10列
• * 表示障碍

题目中的图示显示了从 K 到 H 的一条路径：

K → A → B → C → D → E → F(H)

共需要 5 次跳跃。

注意： 数据保证一定有解。

坐标系统

题目中的图示显示坐标原点在左下角：

• x轴向右（列数）
• y轴向上（行数）

但在输入中，地图是按行从上到下给出的，需要根据具体实现处理坐标转换。

时空限制

• 时间限制：1秒
• 空间限制：64MB