Kapitänin Bovidian rettet ihr Besatzungsmitglied, Doktor Beefalo. Wie bei allen großen Abenteuern ist der Schauplatz folgender: Die Seitenansicht der Welt ist ein zweidimensionales $N \times M$-Gitter ($1 \le N, M \le 500$). Einige Zellen sind leer, andere blockiert und unpassierbar.

Sie kann nicht springen und folgt diesen Regeln.

1. Existiert direkt darunter keine Zelle (Gitterrand), fliegt sie ins Weltall und scheitert.

2. Ist die Zelle darunter leer, fällt sie hinein.

3. Andernfalls: a) Sie darf links oder rechts gehen, wenn die entsprechende Zelle existiert und leer ist. b) Oder die Schwerkraft umkehren.

Umkehren wechselt „darunter“ (Regeln 1, 2) zwischen der Zeile mit einem um 1 höheren und einem um 1 niedrigeren Index. Die erste Eingabezeile hat Index 1, die letzte $N$. Anfangs liegt der höhere Index darunter.

Beefalo ist irgendwo verloren. Erreiche ihre Zelle mit möglichst wenigen Umkehrungen. Falls unmöglich, gib -1 aus.

Eingabe

• Zeile 1: ganze Zahlen $N$, $M$, durch ein Leerzeichen getrennt.
• Zeilen $2..1+N$: Zeile $i+1$ beschreibt Gitterzeile $i$. '.' ist leer, '#' blockiert, 'C' die Startposition der Kapitänin, 'D' die von Beefalo.

Ausgabe

• Zeile 1: ganze Zahl, minimale Umkehrungen bis Beefalo, oder -1 falls unmöglich.

Beispiele

Eingabe 1

5 5
#####
#...#
#...D
#C...
##.##

Ausgabe 1

3

Hinweis

Von (4,2) kehrt sie um, fällt nach (2,2) und geht zweimal rechts nach (2,4). Sie kehrt um, fällt nach (4,4), geht rechts nach (4,5). Zuletzt kehrt sie um und fällt zu Beefalo nach (3,5).

Aufgabenautor: Mark Gordon, 2013