1441: 【提高】骑士牛
时间限制: 1 Sec 内存限制: 128 MB
提交: 8 解决: 4 金币: 3
[提交][状态]题目描述
John用他的一头母牛和Don先生交换了一头“骑士牛”。这头牛有一个独特的能力——在牧场中能像中国象棋中的马一样跑跳(会中国象棋吗?不会?注意:本题不考虑马被“蹩脚”的情况)。当然,这头牛不能跳到岩石或树上,不过能跳到有牧草的地方。这儿有一个宽为X,高为Y的矩形牧场(1 ≤ X ≤ 150; 1 ≤ Y ≤ 150)。 “骑士牛”和其它牛一样喜欢干草。给你一张包含“骑士牛”出发地和树、岩石、灌木或其它障碍物及大包干草等位置信息的地图,确定“骑士牛”得到干草最少要跳几“跳”。地图中“骑士牛”出发地用'K'表示;障碍物用'*'表示,牧草用'.'表示,干草所在地用'H'表示。这儿有一个示例地图:
|
j=1
|
j=2
|
j=3
|
j=4
|
j=5
|
j=6
|
j=7
|
j=8
|
j=9
|
j=10
|
i=1
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
i=2
|
.
|
.
|
.
|
.
|
*
|
.
|
.
|
.
|
.
|
.
|
i=3
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
i=4
|
.
|
.
|
.
|
*
|
.
|
*
|
.
|
.
|
.
|
.
|
i=5
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
*
|
.
|
.
|
i=6
|
.
|
.
|
*
|
.
|
.
|
*
|
.
|
.
|
.
|
H
|
i=7
|
*
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
i=8
|
.
|
.
|
.
|
*
|
.
|
.
|
.
|
*
|
.
|
.
|
i=9
|
.
|
K
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
i=10
|
.
|
.
|
.
|
*
|
.
|
.
|
.
|
.
|
.
|
*
|
i=11
|
.
|
.
|
*
|
.
|
.
|
.
|
.
|
*
|
.
|
.
|
骑士牛得到干草的最少步骤在下图中用ABC……表示,最少要跳5“跳”(其它的路径可能超过5“跳”):
|
j=1
|
j=2
|
j=3
|
j=4
|
j=5
|
j=6
|
j=7
|
j=8
|
j=9
|
j=10
|
i=1
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
i=2
|
.
|
.
|
.
|
.
|
*
|
.
|
.
|
.
|
.
|
.
|
i=3
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
i=4
|
.
|
.
|
.
|
*
|
.
|
*
|
.
|
.
|
.
|
.
|
i=5
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
*
|
.
|
.
|
i=6
|
.
|
.
|
*
|
.
|
.
|
*
|
.
|
.
|
.
|
HF
|
i=7
|
*
|
.
|
.B
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
i=8
|
.
|
.
|
.
|
*
|
.C
|
.
|
.
|
*
|
.E
|
.
|
i=9
|
.
|
KA
|
.
|
.
|
.
|
.
|
.D
|
.
|
.
|
.
|
i=10
|
.
|
.
|
.
|
*
|
.
|
.
|
.
|
.
|
.
|
*
|
i=11
|
.
|
.
|
*
|
.
|
.
|
.
|
.
|
*
|
.
|
.
|
输入
第1行: 两个空格隔开的整数: X 和 Y
第2..Y+1行: 第Y-i+2行包含X个没有空格的字符(就像上面的地图一样):表示第i行的地图。
输出
第1行: 一个单独的整数表示最少的得到干草的“跳”数。所有的数据都能得到干草。
样例输入复制
10 11
..........
....*.....
..........
...*.*....
.......*..
..*..*...H
*.........
...*...*..
.K........
...*.....*
..*....*..
来源
[提交][状态]