題目描述

貪靚嘅 Bitaro 新買咗一張地氈。地氈係長方形，劃分成直 $H$ 行、橫 $W$ 列嘅方格網，每個格仔塗成白色或者黑色。地氈由上而下第 $i$ 行、由左至右第 $j$ 列（$1 \le i \le H$，$1 \le j \le W$）嘅格仔顏色，喺字符串 $S_i$ 嘅第 $j$ 個字符係 . 嗰陣係白色，係 # 嗰陣係黑色。

Bitaro 諗到一個遊戲：喺地氈最左上角嘅格仔放一隻棋，透過做幾次以下操作，令隻棋去到地氈最右下角嘅格仔。

• 揀 $1$ 個同隻棋而家所在格仔唔同顏色、而且上下左右相鄰嘅格仔，將隻棋移去嗰個格仔度。

Bitaro 希望去到終點所需嘅操作次數越少越好。不過，視乎地氈嘅圖案，亦有可能去唔到。

給定地氈圖案嘅資訊，請編寫一個程式，判斷透過重複操作可唔可以令隻棋由左上角嘅格仔去到右下角嘅格仔；如果可以，求出操作次數嘅最小值。

數據範圍

• $1 \le H \le 500$。
• $1 \le W \le 500$。
• $(H, W) \neq (1, 1)$。
• $S_i$ 係長度為 $W$ 嘅字符串（$1 \le i \le H$）。
• $S_i$ 嘅每個字符係 . 或者 #（$1 \le i \le H$）。
• $H, W$ 係整數。

子任務

1. （$4$ 分）$H = 1$。
2. （$14$ 分）$H \le 5$，$W \le 5$。
3. （$24$ 分）$H \le 30$，$W \le 30$。
4. （$58$ 分）無額外限制。

輸入格式

輸入由標準輸入按以下格式給出：

H W
S_1
S_2
:
S_H

輸出格式

如果透過重複操作可以令隻棋由左上角嘅格仔去到右下角嘅格仔，就輸出操作次數嘅最小值；如果唔可能，就輸出 -1。喺標準輸出用 $1$ 行輸出。

樣例

樣例輸入 1

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

樣例輸出 1

9

例如，可以考慮好似圖入面噉樣嘅操作。

喺左邊嘅例子用 $9$ 次操作、喺右邊嘅例子用 $13$ 次操作，都可以令隻棋由左上角嘅格仔去到右下角嘅格仔。

因為唔可能用少過 $9$ 次操作去到，所以輸出 $9$。

呢個樣例輸入滿足子任務 $2, 3, 4$ 嘅限制。

樣例輸入 2

3 3
...
...
...

樣例輸出 2

-1

亦都有可能由一開始就做唔到任何操作。喺呢種情況下，因為唔可能令隻棋去到右下角嘅格仔，所以輸出 -1。

呢個樣例輸入滿足子任務 $2, 3, 4$ 嘅限制。

樣例輸入 3

1 5
.#.#.

樣例輸出 3

4

呢個樣例輸入滿足所有子任務嘅限制。

樣例輸入 4

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

樣例輸出 4

12

呢個樣例輸入滿足子任務 $2, 3, 4$ 嘅限制。

樣例輸入 5

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

樣例輸出 5

12

呢個樣例輸入滿足子任務 $3, 4$ 嘅限制。