Descrizione del problema

Bitaro, amante della moda, ha comprato un tappeto nuovo. Il tappeto ha una forma rettangolare suddivisa in una griglia di $H$ righe in verticale e $W$ colonne in orizzontale, e ogni casella è colorata di bianco oppure di nero. Il colore della casella situata nella $i$-esima riga dall'alto e nella $j$-esima colonna da sinistra ($1 \le i \le H$, $1 \le j \le W$) del tappeto è bianco quando il $j$-esimo carattere della stringa $S_i$ è ., ed è nero quando è #.

Bitaro ha ideato un gioco in cui posiziona una pedina sulla casella più in alto a sinistra del tappeto e, eseguendo più volte la seguente operazione, fa arrivare la pedina sulla casella più in basso a destra del tappeto:

• Scegli $1$ casella di colore diverso da quella su cui si trova attualmente la pedina e ad essa adiacente in verticale o in orizzontale, e sposta la pedina su tale casella.

Bitaro vorrebbe ridurre al minimo il numero di operazioni necessarie per arrivare a destinazione. Tuttavia, a seconda del motivo del tappeto, potrebbe essere impossibile far arrivare la pedina a destinazione.

Date le informazioni sul motivo del tappeto, scrivi un programma per stabilire se sia possibile far arrivare la pedina dalla casella in alto a sinistra alla casella in basso a destra ripetendo l'operazione e, in caso affermativo, trovare il numero minimo di operazioni.

Vincoli

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$ è una stringa di lunghezza $W$ ($1 \le i \le H$).
• Ogni carattere di $S_i$ è . oppure # ($1 \le i \le H$).
• $H, W$ sono numeri interi.

Sottoproblemi

1. ($4$ punti) $H = 1$.
2. ($14$ punti) $H \le 5$, $W \le 5$.
3. ($24$ punti) $H \le 30$, $W \le 30$.
4. ($58$ punti) Nessun vincolo aggiuntivo.

Dati di input

L'input viene fornito dallo standard input nel seguente formato:

H W
S_1
S_2
:
S_H

Dati di output

Se è possibile far arrivare la pedina dalla casella in alto a sinistra alla casella in basso a destra ripetendo l'operazione, stampa il numero minimo di operazioni; se è impossibile, stampa -1, in $1$ riga sullo standard output.

Esempi di input/output

Input di esempio 1

4 5
...#.
#####
...#.
#.###

Output di esempio 1

9

Ad esempio, si possono considerare le operazioni mostrate nella figura.

Nell'esempio a sinistra è possibile far arrivare la pedina dalla casella in alto a sinistra alla casella in basso a destra in $9$ operazioni, mentre nell'esempio a destra in $13$ operazioni.

Poiché è impossibile arrivarci in meno di $9$ operazioni, si stampa $9$.

Questo esempio di input soddisfa i vincoli dei Sottoproblemi $2, 3, 4$.

Input di esempio 2

3 3
...
...
...

Output di esempio 2

-1

Ci sono casi in cui non è possibile eseguire alcuna operazione fin dall'inizio. In questo caso, poiché è impossibile far arrivare la pedina alla casella in basso a destra, si stampa -1.

Questo esempio di input soddisfa i vincoli dei Sottoproblemi $2, 3, 4$.

Input di esempio 3

1 5
.#.#.

Output di esempio 3

4

Questo esempio di input soddisfa i vincoli di tutti i sottoproblemi.

Input di esempio 4

5 5
###.#
.#...
.#..#
.####
##..#

Output di esempio 4

12

Questo esempio di input soddisfa i vincoli dei Sottoproblemi $2, 3, 4$.

Input di esempio 5

7 5
.#.##
##...
.#.##
.###.
##.#.
...#.
##.#.

Output di esempio 5

12

Questo esempio di input soddisfa i vincoli dei Sottoproblemi $3, 4$.