La capitaine Bovidian part sauver sa coéquipière, le docteur Beefalo. Comme dans toute grande aventure, le monde vu de côté est une grille bidimensionnelle $N \times M$ ($1 \le N, M \le 500$). Certaines cases sont vides, d’autres bloquées et infranchissables.

Elle ne peut pas sauter et doit suivre ces règles physiques.

1. S’il n’existe pas de case directement dessous (bord de la grille), elle s’envole dans l’espace et échoue.

2. Si la case dessous est vide, elle y tombe.

3. Sinon : a) Elle peut aller à gauche ou à droite si la case correspondante existe et est vide. b) Ou inverser la gravité.

L’inversion échange le « dessous » (règles 1, 2) entre la ligne d’indice supérieur de 1 et celle d’indice inférieur de 1. La première ligne d’entrée est 1, la dernière $N$. Au départ, dessous signifie l’indice supérieur de 1.

Beefalo est perdue dans ce monde. Atteignez sa case avec le moins d’inversions possible. Si c’est impossible, affichez -1.

Entrée

• Ligne 1 : entiers $N$, $M$ séparés par un espace.
• Lignes $2..1+N$ : la ligne $i+1$ décrit la rangée $i$. '.' signifie vide, '#' bloquée, 'C' le départ de la capitaine et 'D' celui de Beefalo.

Sortie

• Ligne 1 : entier, nombre minimal d’inversions pour rejoindre Beefalo, ou -1 si impossible.

Exemples

Entrée 1

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

Sortie 1

3

Remarque

De (4,2), elle inverse, tombe en (2,2), puis va deux fois à droite en (2,4). Elle inverse, tombe en (4,4), va à droite en (4,5). Enfin elle inverse et tombe sur Beefalo en (3,5).

Auteur du problème : Mark Gordon, 2013