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.

题目背景

在中国传统文化里，牛象征着勤劳、坚韧与奉献。古代社会中，牛不仅是重要的农业生产工具，也被赋予了吃苦耐劳的精神特质。

马则代表着速度、力量与自由。历史上，马是战争与交通的重要组成部分，象征着勇往直前和无拘无束的生活态度。

将两者结合，“牛马”一词往往用来比喻那些勤勉工作、任劳任怨的人，暗示这类人像牛一样辛勤耕耘、像马一般不知疲倦地奔跑。但在网络语境中，“牛马”有时也会带有一定的贬义色彩，用以形容被过度剥削或处于恶劣工作环境下的工作者。

吝啬的老板想进一步优化公司效益，于是真的养了一匹牛马，以代替劳动工作者。这头神奇的牛马像其它牛一样喜欢吃草，但是行走方式却是中国象棋中马的走法（马走日）。

问题描述

给你一张地图，上面标注了牛马起始位置，树、灌木、石头以及其它障碍的位置，除此之外还有一捆草。这头神奇的牛马不能跳到树上和石头等障碍物上。

我们把牧场用一个 x，y 的坐标图来表示。牛马的位置用 K 来标记，障碍的位置用 * 来标记，草的位置用 H 来标记。

请确定牛马要想吃到草，至少需要跳多少次。

输入

第 1 行： 两个数，表示农场的列数 C 和行数 R。

第 2..R+1 行: 每行一个由 C 个字符组成的字符串，共同描绘出牧场地图。

输出

一个整数，表示跳跃的最小次数。

样例

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

5

数据范围

1≤R,C≤150。数据保证有解。

每个测试用例时间限制1s，内存限制256MB。