Aufgabenbeschreibung

Der modebewusste Bitaro hat sich einen neuen Teppich zugelegt. Der Teppich hat eine rechteckige Form, die in ein Gitter aus vertikal $H$ Zeilen und horizontal $W$ Spalten unterteilt ist, wobei jedes Feld entweder weiß oder schwarz gefärbt ist. Die Farbe des Feldes in der $i$-ten Zeile von oben und der $j$-ten Spalte von links ($1 \le i \le H$, $1 \le j \le W$) des Teppichs ist weiß, wenn das $j$-te Zeichen der Zeichenkette $S_i$ ein . ist, und schwarz, wenn es ein # ist.

Bitaro hat sich ein Spiel ausgedacht, bei dem er einen Spielstein auf das Feld ganz oben links auf dem Teppich setzt und versucht, diesen durch mehrmaliges Ausführen der folgenden Operation auf das Feld ganz unten rechts auf dem Teppich zu bringen:

• Wähle $1$ Feld aus, das eine andere Farbe als das Feld hat, auf dem sich der Spielstein aktuell befindet, und das vertikal oder horizontal daran angrenzt, und bewege den Spielstein auf dieses Feld.

Bitaro möchte die Anzahl der Operationen bis zum Ziel so gering wie möglich halten. Je nach Muster des Teppichs ist es jedoch möglicherweise gar nicht machbar, das Ziel zu erreichen.

Schreibe ein Programm, das anhand der Informationen über das Teppichmuster entscheidet, ob der Spielstein durch Wiederholen der Operation vom Feld oben links zum Feld unten rechts gelangen kann, und falls ja, die minimale Anzahl an Operationen berechnet.

Einschränkungen

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$ ist eine Zeichenkette der Länge $W$ ($1 \le i \le H$).
• Jedes Zeichen von $S_i$ ist . oder # ($1 \le i \le H$).
• $H, W$ sind ganze Zahlen.

Teilaufgaben

1. ($4$ Punkte) $H = 1$.
2. ($14$ Punkte) $H \le 5$, $W \le 5$.
3. ($24$ Punkte) $H \le 30$, $W \le 30$.
4. ($58$ Punkte) Keine weiteren Einschränkungen.

Eingabe

Die Eingabe erfolgt über die Standardeingabe im folgenden Format:

H W
S_1
S_2
:
S_H

Ausgabe

Gib auf der Standardausgabe in $1$ Zeile die minimale Anzahl an Operationen aus, falls es möglich ist, den Spielstein durch Wiederholen der Operation vom Feld oben links zum Feld unten rechts zu bringen, oder -1, falls dies unmöglich ist.

Beispiele

Beispiel-Eingabe 1

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

Beispiel-Ausgabe 1

9

Beispielsweise sind die in der Abbildung dargestellten Operationen denkbar.

Im linken Beispiel kann der Spielstein in $9$ Operationen und im rechten Beispiel in $13$ Operationen vom Feld oben links zum Feld unten rechts gebracht werden.

Da es unmöglich ist, das Ziel in weniger als $9$ Operationen zu erreichen, wird $9$ ausgegeben.

Dieses Eingabebeispiel erfüllt die Einschränkungen der Teilaufgaben $2, 3, 4$.

Beispiel-Eingabe 2

3 3
...
...
...

Beispiel-Ausgabe 2

-1

Es gibt auch Fälle, in denen von Anfang an keine Operation möglich ist. Da der Spielstein in diesem Fall das Feld unten rechts nicht erreichen kann, wird -1 ausgegeben.

Dieses Eingabebeispiel erfüllt die Einschränkungen der Teilaufgaben $2, 3, 4$.

Beispiel-Eingabe 3

1 5
.#.#.

Beispiel-Ausgabe 3

4

Dieses Eingabebeispiel erfüllt die Einschränkungen aller Teilaufgaben.

Beispiel-Eingabe 4

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

Beispiel-Ausgabe 4

12

Dieses Eingabebeispiel erfüllt die Einschränkungen der Teilaufgaben $2, 3, 4$.

Beispiel-Eingabe 5

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

Beispiel-Ausgabe 5

12

Dieses Eingabebeispiel erfüllt die Einschränkungen der Teilaufgaben $3, 4$.