Kapitan Bovidian wyrusza ratować członkinię załogi, doktor Beefalo. Jak we wszystkich wielkich przygodach, świat widziany z boku to dwuwymiarowa siatka $N \times M$ ($1 \le N, M \le 500$). Pola są puste lub zablokowane i nieprzechodnie.
Nie może skakać i przestrzega tych zasad fizyki.
Jeśli bezpośrednio pod nią nie ma pola (brzeg siatki), wylatuje w kosmos i przegrywa misję.
Jeśli pole pod nią jest puste, spada na nie.
W przeciwnym razie: a) Może iść w lewo lub prawo, jeśli odpowiednie pole istnieje i jest puste. b) Albo odwrócić kierunek grawitacji.
Odwrócenie przełącza „pod” (zasady 1, 2) między wierszem o indeksie o 1 większym i o 1 mniejszym. Pierwszy wiersz wejścia ma 1, ostatni $N$. Początkowo pod nią jest większy indeks.
Doktor zaginęła. Dotrzyj do jej pola minimalną liczbą odwróceń. Jeśli niemożliwe, wypisz -1.
Wejście
- Wiersz 1: całkowite $N$, $M$ oddzielone spacją.
- Wiersze $2..1+N$: wiersz $i+1$ opisuje wiersz świata $i$. '.' to puste pole, '#' zablokowane, 'C' start kapitan, 'D' start doktor.
Wyjście
- Wiersz 1: liczba całkowita, minimum odwróceń do celu, lub -1 jeśli niemożliwe.
Przykład
Wejście 1
5 5 ##### #...# #...D #C... ##.##
Wyjście 1
3
Uwagi
Z (4,2) odwraca grawitację i spada do (2,2), idzie dwa razy w prawo do (2,4). Odwraca i spada do (4,4), idzie w prawo do (4,5). Na koniec odwraca i spada do doktor w (3,5).
Autor zadania: Mark Gordon, 2013