題目描述

熱愛時尚的 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$ 的限制。