【提高】骑士牛 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

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

题目描述

输入格式

输出格式

样例