A capitã Bovidian resgata sua tripulante, a doutora Beefalo. Como em toda grande aventura, o mundo visto de lado é uma grade bidimensional $N \times M$ ($1 \le N, M \le 500$). Há células vazias e bloqueadas, que não podem ser atravessadas.
Ela não pula e segue estas regras físicas.
Sem célula diretamente abaixo (borda da grade), voa ao espaço e falha.
Se a célula abaixo é vazia, cai nela.
Caso contrário: a) Pode ir à esquerda ou direita se a célula correspondente existe e é vazia. b) Ou inverter a gravidade.
A inversão troca o «abaixo» (regras 1, 2) entre a linha com índice um maior e um menor. A primeira linha da entrada é 1, a última $N$. Inicialmente abaixo é o índice um maior.
A doutora está perdida. Alcance sua célula com o mínimo de inversões. Se impossível, imprima -1.
Entrada
- Linha 1: inteiros $N$, $M$ separados por um espaço.
- Linhas $2..1+N$: a linha $i+1$ descreve a linha $i$ do mundo. '.' é vazia, '#' bloqueada, 'C' o início da capitã e 'D' o da doutora.
Saída
- Linha 1: inteiro com o mínimo de inversões para chegar, ou -1 se impossível.
Exemplos
Entrada 1
5 5 ##### #...# #...D #C... ##.##
Saída 1
3
Nota
De (4,2), inverte e cai em (2,2), depois vai duas vezes à direita até (2,4). Inverte e cai em (4,4), vai à direita até (4,5). Finalmente inverte e cai junto à doutora em (3,5).
Créditos do problema: Mark Gordon, 2013