Problembeskrivelse

Moteinteresserte Bitaro har skaffet seg et nytt teppe. Teppet har form som et rektangel delt inn i et rutenett med $H$ rader loddrett og $W$ kolonner vannrett, og hver rute er farget enten hvit eller svart. Fargen på ruten i den $i$-te raden ovenfra og den $j$-te kolonnen fra venstre ($1 \le i \le H$, $1 \le j \le W$) på teppet er hvit når det $j$-te tegnet i strengen $S_i$ er ., og svart når det er #.

Bitaro kom på en lek der han plasserer en brikke på ruten lengst oppe til venstre på teppet, og ved å utføre følgende operasjon noen ganger får brikken til å nå ruten lengst nede til høyre på teppet:

• Velg $1$ rute som har en annen farge enn ruten der brikken står nå, og som grenser til den over, under, til venstre eller til høyre, og flytt brikken til denne ruten.

Bitaro ønsker at antallet operasjoner for å nå målet skal være så lite som mulig. Avhengig av mønsteret på teppet er det imidlertid ikke sikkert at det er mulig å nå frem.

Gitt informasjonen om mønsteret på teppet, skriv et program som avgjør om det er mulig å få brikken til å nå fra ruten øverst til venstre til ruten nederst til høyre ved å gjenta operasjonen, og hvis det er mulig, finner det minste antallet operasjoner.

Begrensninger

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$ er en streng med lengde $W$ ($1 \le i \le H$).
• Hvert tegn i $S_i$ er . eller # ($1 \le i \le H$).
• $H, W$ er heltall.

Deloppgaver

1. ($4$ poeng) $H = 1$.
2. ($14$ poeng) $H \le 5$, $W \le 5$.
3. ($24$ poeng) $H \le 30$, $W \le 30$.
4. ($58$ poeng) Ingen ytterligere begrensninger.

Inndata

Inndataen gis fra standard inndata i følgende format:

H W
S_1
S_2
:
S_H

Utdata

Hvis det er mulig å få brikken til å nå fra ruten øverst til venstre til ruten nederst til høyre ved å gjenta operasjonen, skriv ut det minste antallet operasjoner; hvis det er umulig, skriv ut -1 på $1$ linje til standard utdata.

Eksempler

Eksempelinndata 1

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

Eksempelutdata 1

9

For eksempel kan man tenke seg operasjonene vist på figuren.

I eksempelet til venstre er det mulig å få brikken fra ruten øverst til venstre til ruten nederst til høyre på $9$ operasjoner, og i eksempelet til høyre på $13$ operasjoner.

Siden det er umulig å nå frem på færre enn $9$ operasjoner, skrives det ut $9$.

Dette eksempelet oppfyller begrensningene for deloppgavene $2, 3, 4$.

Eksempelinndata 2

3 3
...
...
...

Eksempelutdata 2

-1

Det finnes også tilfeller der ingen operasjoner kan utføres helt fra starten av. I dette tilfellet er det umulig å få brikken til ruten nederst til høyre, så det skrives ut -1.

Dette eksempelet oppfyller begrensningene for deloppgavene $2, 3, 4$.

Eksempelinndata 3

1 5
.#.#.

Eksempelutdata 3

4

Dette eksempelet oppfyller begrensningene for alle deloppgaver.

Eksempelinndata 4

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

Eksempelutdata 4

12

Dette eksempelet oppfyller begrensningene for deloppgavene $2, 3, 4$.

Eksempelinndata 5

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

Eksempelutdata 5

12

Dette eksempelet oppfyller begrensningene for deloppgavene $3, 4$.