Problembeskrivning

Modeälskaren Bitaro har skaffat en ny matta. Mattan har formen av en rektangel uppdelad i ett rutnät med $H$ rader vertikalt och $W$ kolumner horisontellt, där varje ruta är målad antingen vit eller svart. Färgen på rutan på den $i$-te raden uppifrån och den $j$-te kolumnen från vänster ($1 \le i \le H$, $1 \le j \le W$) på mattan är vit när det $j$-te tecknet i strängen $S_i$ är ., och svart när det är #.

Bitaro kom på en lek där han placerar en pjäs på rutan längst upp till vänster på mattan och genom att utföra följande operation ett antal gånger får pjäsen att nå rutan längst ner till höger på mattan:

• Välj $1$ ruta som har en annan färg än rutan där pjäsen står för tillfället och som gränsar till den uppåt, nedåt, åt vänster eller åt höger, och flytta pjäsen till den rutan.

Bitaro vill att antalet operationer för att nå målet ska vara så litet som möjligt. Beroende på mattans mönster är det dock inte säkert att det går att nå fram.

Givet informationen om mattans mönster, skriv ett program som avgör om det är möjligt att få pjäsen att nå från den översta vänstra rutan till den nedersta högra rutan genom att upprepa operationen, och om det är möjligt, bestämmer det minsta antalet operationer.

Begränsningar

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$ är en sträng med längden $W$ ($1 \le i \le H$).
• Varje tecken i $S_i$ är . eller # ($1 \le i \le H$).
• $H, W$ är heltal.

Deluppgifter

1. ($4$ poäng) $H = 1$.
2. ($14$ poäng) $H \le 5$, $W \le 5$.
3. ($24$ poäng) $H \le 30$, $W \le 30$.
4. ($58$ poäng) Inga ytterligare begränsningar.

Indata

Indatan ges från standardindata i följande format:

H W
S_1
S_2
:
S_H

Utdata

Om det är möjligt att få pjäsen att nå från den översta vänstra rutan till den nedersta högra rutan genom att upprepa operationen, skriv ut det minsta antalet operationer; om det är omöjligt, skriv ut -1 på $1$ rad till standardutdata.

Exempel

Indataexempel 1

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

Utdataexempel 1

9

Till exempel kan man tänka sig operationerna som visas i figuren.

I det vänstra exemplet går det att få pjäsen att nå från den översta vänstra rutan till den nedersta högra rutan på $9$ operationer, och i det högra exemplet på $13$ operationer.

Eftersom det är omöjligt att nå fram på färre än $9$ operationer skrivs $9$ ut.

Detta indataexempel uppfyller begränsningarna för deluppgifterna $2, 3, 4$.

Indataexempel 2

3 3
...
...
...

Utdataexempel 2

-1

Det finns fall där ingen operation kan utföras redan från början. I detta fall är det omöjligt att få pjäsen att nå den nedersta högra rutan, så -1 skrivs ut.

Detta indataexempel uppfyller begränsningarna för deluppgifterna $2, 3, 4$.

Indataexempel 3

1 5
.#.#.

Utdataexempel 3

4

Detta indataexempel uppfyller begränsningarna för alla deluppgifter.

Indataexempel 4

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

Utdataexempel 4

12

Detta indataexempel uppfyller begränsningarna för deluppgifterna $2, 3, 4$.

Indataexempel 5

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

Utdataexempel 5

12

Detta indataexempel uppfyller begränsningarna för deluppgifterna $3, 4$.