Farmer John trocou uma de suas vacas pela que Farmer Don chama «The Knight». Salta como cavalo de xadrez: duas casas de lado e uma acima, ou duas abaixo e uma de lado etc. Não pousa em pedras ou árvores, mas percorre bem o pasto de $X$ por $Y$ casas ($1 \le X \le 150$; $1 \le Y \le 150$).

«The Knight» gosta de feno. Dado mapa do início, árvores, arbustos, pedras e outros obstáculos e um fardo de feno, determine quantos saltos precisa. K é a vaca, * obstáculos, H feno. Mapa típico:

                    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

O caminho A, B, C etc. chega em 5 saltos (pode haver outros caminhos de comprimento 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

Dica: provavelmente é mais fácil usar uma fila simples, primeiro a entrar, primeiro a sair, implementada com alguns vetores paralelos.

Entrada

• Linha 1: dois inteiros $X$, $Y$ separados por espaço.
• Linhas $2..Y+1$: linha $Y-i+2$, $X$ caracteres sem espaços, linha $i$ do mapa (na ordem mostrada acima).

Saída

• Linha 1: inteiro, mínimo de saltos ao feno. Sempre é possível chegar.

Exemplos

Entrada 1

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

Saída 1

5

Autor do problema: Rob Kolstad, 2009