#7097. 【提高】骑士牛 USACO 普及−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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行: 一个单独的整数表示最少的得到干草的“跳”数。所有的数据都能得到干草。

样例

样例输入1

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

样例输出1

5