Description
题目描述
小张用他的一头母牛和吴先生交换了一头“牛骑士”。这头牛有一个独特的能力——在牧场中能像中国象棋中的马一样跑跳（会中国象棋吗？不会？）。当然，这头牛不能跳到岩石或树上，不过能跳到有牧草的地方。这儿有一个宽为X，高为Y的矩形牧场(1 <= X <= 150; 1 <= Y <= 150)。“牛骑士”和其它牛一样喜欢干草。给你一张包含“牛骑士”出发地和树、岩石、灌木或其它障碍物及大包干草等位置信息的地图，确定“牛骑士”得到干草要跳几“跳”。地图中“牛骑士”出发地用'K'表示；障碍物用'*'表示，牧草用'.'表示，干草所在地用'H'表示。如下图。
“牛骑士”在格子中，有8个方向可以探索。探索顺序按右图中的序号顺序进行。而且“牛骑士”的思维是“一根筋”式的，它会在每一个点按照图中的方向顺序进行探索，也即1号方向能走就走1号方向，不能走才会考虑2号方向，以此类推，直到找到干草为止。
上图中得到干草的步骤在下图中用A,B,C……表示，需要跳4“跳”（如下图）。
Input
第1行，两个空格隔开的整数: X 和 Y 接下来有Y行，每行包含X个没有空格的字符，表示这一行的地图。
Output
一行，一个单独的整数，表示在这种探索顺序下找到干草的“跳”数。所有的数据都能得到干草。
Sample Input Copy
10 11
..........
....*K....
..........
...*.*....
.......*..
..*..*...H
*.........
...*...*..
..........
...*.....*
..*....*..Sample Output Copy
4