Farmer John ha scambiato una delle sue mucche con quella che Farmer Don chiama «The Knight». Salta come un cavallo negli scacchi: due caselle di lato e una su, o due giù e una di lato, ecc. Non atterra su rocce o alberi, ma si muove bene nel pascolo di $X$ per $Y$ caselle ($1 \le X \le 150$; $1 \le Y \le 150$).
«The Knight» ama il fieno. Dati partenza, alberi, cespugli, rocce e altri ostacoli e una balla di fieno sulla mappa, trova quanti salti servono. K è la mucca, * ostacoli, H fieno. Mappa tipica:
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 0Il percorso A, B, C, ecc. arriva in 5 salti (potrebbero esserci altri percorsi lunghi 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 0Suggerimento: probabilmente è più semplice usare una coda primo entrato, primo uscito, implementata con pochi array paralleli.
Input
- Riga 1: due interi $X$, $Y$ separati da spazio.
- Righe $2..Y+1$: riga $Y-i+2$, $X$ caratteri senza spazi per la riga $i$ della mappa (nell'ordine illustrato sopra).
Output
- Riga 1: intero, minimo di salti al fieno. È sempre raggiungibile.
Esempi
Input 1
10 11 .......... ....*..... .......... ...*.*.... .......*.. ..*..*...H *......... ...*...*.. .K........ ...*.....* ..*....*..
Output 1
5
Autore del problema: Rob Kolstad, 2009