La capitana Bovidian busca rescatar a su tripulante, la doctora Beefalo. Como en toda gran aventura, el mundo visto de lado es una cuadrícula bidimensional $N \times M$ ($1 \le N, M \le 500$). Hay celdas vacías y bloqueadas que no se pueden atravesar.
No puede saltar y debe seguir estas reglas físicas.
Si no existe celda justo debajo (borde de la cuadrícula), sale volando al espacio y fracasa.
Si la celda debajo está vacía, cae en ella.
En otro caso: a) Puede ir a izquierda o derecha si la celda correspondiente existe y está vacía. b) O invertir la gravedad.
Invertir cambia «debajo» (reglas 1, 2) entre la fila con índice uno mayor y uno menor. La primera fila de entrada es 1, la última $N$. Inicialmente debajo es el índice uno mayor.
La doctora está perdida. Llega a su celda con el mínimo de inversiones. Si es imposible, escribe -1.
Entrada
- Línea 1: enteros $N$, $M$ separados por un espacio.
- Líneas $2..1+N$: la línea $i+1$ describe la fila $i$. '.' es vacía, '#' bloqueada, 'C' el inicio de la capitana y 'D' el de la doctora.
Salida
- Línea 1: entero con el mínimo de inversiones para llegar, o -1 si es imposible.
Ejemplos
Entrada 1
5 5 ##### #...# #...D #C... ##.##
Salida 1
3
Nota
Desde (4,2) invierte y cae en (2,2), luego va dos veces a la derecha hasta (2,4). Invierte y cae en (4,4), va a la derecha hasta (4,5). Finalmente invierte y cae junto a la doctora en (3,5).
Autor del problema: Mark Gordon, 2013