La capitana Bovidian parte per salvare la compagna di equipaggio, la dottoressa Beefalo. Come in ogni grande avventura, il mondo visto di lato è una griglia bidimensionale $N \times M$ ($1 \le N, M \le 500$). Alcune celle sono vuote, altre bloccate e non attraversabili.
Non può saltare e segue queste regole fisiche.
Se non esiste una cella subito sotto (bordo della griglia), vola nello spazio e fallisce.
Se la cella sotto è vuota, cade in essa.
Altrimenti: a) Può andare a sinistra o destra se la cella corrispondente esiste ed è vuota. b) Oppure invertire la gravità.
Invertire cambia il «sotto» (regole 1, 2) fra la riga con indice uno maggiore e uno minore. La prima riga dell’input è 1, l’ultima $N$. Inizialmente sotto è l’indice uno maggiore.
La dottoressa si è persa. Raggiungi la sua cella con il minimo di inversioni. Se impossibile, stampa -1.
Input
- Riga 1: interi $N$, $M$ separati da uno spazio.
- Righe $2..1+N$: la riga $i+1$ descrive la riga $i$ del mondo. '.' è vuota, '#' bloccata, 'C' l’inizio della capitana e 'D' quello della dottoressa.
Output
- Riga 1: intero con il minimo di inversioni per raggiungerla, o -1 se impossibile.
Esempi
Input 1
5 5 ##### #...# #...D #C... ##.##
Output 1
3
Note
Da (4,2) inverte e cade in (2,2), poi va due volte a destra fino a (2,4). Inverte e cade in (4,4), va a destra fino a (4,5). Infine inverte e cade dalla dottoressa in (3,5).
Autore del problema: Mark Gordon, 2013