Farmer John tauschte eine seiner Kühe gegen jene, die Farmer Don „The Knight“ nennt. Sie springt wie ein Schachspringer: zwei Felder seitlich, eins hoch, oder zwei runter, eins seitlich usw. Sie darf nicht auf Felsen oder Bäumen landen, bewegt sich sonst gut auf der Weide aus $X$ mal $Y$ Feldern ($1 \le X \le 150$; $1 \le Y \le 150$).

„The Knight“ mag Heu. Gegeben sind Start, Bäume, Büsche, Felsen und andere Hindernisse sowie ein Heuballen. Wie viele Sprünge dorthin? K ist die Kuh, * Hindernisse, H Heu. Typische Karte:

                    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

Der Weg A, B, C usw. erreicht das Heu in 5 Sprüngen (andere Wege der Länge 5 sind möglich):

                    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

Hinweis: Am einfachsten ist wohl eine einfache Warteschlange nach dem Prinzip zuerst hinein, zuerst hinaus, aus wenigen parallelen Arrays.

Eingabe

• Zeile 1: zwei Ganzzahlen $X$, $Y$ durch Leerzeichen getrennt.
• Zeilen $2..Y+1$: Zeile $Y-i+2$ enthält $X$ Zeichen ohne Leerzeichen für Kartenreihe $i$ (in der dargestellten Reihenfolge eingelesen).

Ausgabe

• Zeile 1: Ganzzahl, minimale Sprungzahl zum Heu. Erreichbarkeit ist garantiert.

Beispiele

Eingabe 1

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

Ausgabe 1

5

Aufgabenautor: Rob Kolstad, 2009