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

骑士牛得到干草的最少步骤在下图中用 ABC…… 表示，最少要跳 5 “跳”（其它的路径可能超过 5 “跳”）：

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

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

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

广搜

广搜