Description

这头神奇的牛像其它牛一样喜欢吃草，给你一张地图，上面标注了The  Knight的开始位置，树、灌木、石头以及其它障碍的位置，除此之外还有一捆草。现在你的任务是，确定The  Knight要想吃到草，至少需要跳多少次。The  Knight的位置用'K'来标记，障碍的位置用'*'来标记，草的位置用'H'来标记。这里有一个地图的例

Input Format

第一行：  两个数，表示农场的列数(< =150)和行数(< =150) 第二行..结尾:  如题目描述的图。

Output Format

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

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

5

Hint

Hint：这类问题可以用一个简单的先进先出表（队列）来解决。

提示，方向数组为

 int dir[8][2]={{2,1},{-2,1},{2,-1},{-2,-1},{-1,2},{1,2},{-1,-2},{1,-2}};//方向数组

Source

搜索