Farmer John échange une de ses vaches contre celle que Farmer Don appelle «The Knight». Elle saute comme un cavalier d'échecs : deux cases de côté, une vers le haut, ou deux vers le bas, une de côté, etc. Elle ne peut atterrir sur rochers ou arbres, mais parcourt aisément le pâturage de $X$ par $Y$ cases ($1 \le X \le 150$ ; $1 \le Y \le 150$).

«The Knight» aime aussi le foin. La carte donne son départ, arbres, buissons, rochers et autres obstacles et une botte de foin. Combien de sauts pour y parvenir ? K est la vache, * les obstacles, H le foin. Carte typique :

                    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

Le chemin A, B, C, etc. atteint le foin en 5 sauts (d'autres chemins de longueur 5 sont possibles) :

                    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

Indication : une simple file premier entré, premier sorti, réalisée par quelques tableaux parallèles, est probablement la solution la plus facile.

Entrée

• Ligne 1 : deux entiers $X$, $Y$ séparés par un espace.
• Lignes $2..Y+1$ : ligne $Y-i+2$, $X$ caractères sans espaces, rangée $i$ de la carte (lue dans l'ordre du schéma ci-dessus).

Sortie

• Ligne 1 : un entier, le nombre minimal de sauts vers le foin. Il est toujours accessible.

Exemples

Entrée 1

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

Sortie 1

5

Auteur du problème : Rob Kolstad, 2009