#99. 象棋中马的走法

象棋中马的走法

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你掉进了一个巨大的棋盘里面,里面只有行和列,姑且用一个平面直角的坐标系来表示。你只能像中国象棋中的马一样行走,你的起始位置用’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

你可以按照下图中的A,B,C,D``…`这条路径用5\red 5次去到出口(不排除其它路线也是5\red 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

输入格式

第1行: 两个数,表示棋盘的列数L(L<=150)\red{L(L<=150)}和行数H(H<=150)\red{H(H<=150)}

第2..R+1行: 每行一个由L\red{L}个字符组成的字符串,这就是地图。

输出格式

一个整数,即最小次数。

样例

输入样例

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

输出样例

5

提示

注意: 数据保证一定有解。

七中集训 part5

未参加
状态
已结束
规则
IOI
题目
7
开始于
2024-1-25 9:00
结束于
2024-2-15 5:00
持续时间
500 小时
主持人
参赛人数
17