【tyvj1074】武士风度的牛

2013年12月7日1,4020

题目描述

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

这里有一个地图的例子:
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 可以按照下图中的A,B,C,D…这条路径用5次跳到草的地方(有可能其它路线的长度也是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

输入

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

输出

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

样例输入

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

样例输出

5

提示

Hint:这类问题可以用一个简单的先进先出表(队列)来解决。

代码