#}. 【提高】骑士牛

    Type: Default 1000ms 128MiB

【提高】骑士牛

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

说明

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........
...*.....*
..*....*..
5

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45