Walk or Break

問題文

$H \times W$ の大きさの迷路があります。
上から $i$ 行目、左から $j$ 列目のマスは文字 $a_{i,j}$ で与えられ、$a_{i,j}$ は . , # のいずれかです。

• . は道であり、移動可能
• # は壁であり、移動不可

さめくんは $1$ 秒ごとに以下のいずれかの行動をします。

• 現在いるマスから上下左右のいずれか 1 マスの道 . を選び、選んだマスに移動する
• 現在いるマスから上下左右のいずれか 1 マスの壁 # を選び、選んだマスを壊して 道 . にする

さめくんが $a_{1,1}$ から $a_{H,W}$ に移動するのに必要な最短の時間を求めてください。

制約

$2 \le H,W \le 100$
$a_{i,j}$ は . , # のいずれか
$a_{1,1}$ と $a_{H,W}$ は 道 . である

入力

出力

答えを出力してください。

入力例1

3 3
..#
###
#..

出力例1

5

以下のような手順で 5 秒で移動できます

(1,1) から (1,2) へ移動
(2,2) の壁を壊して道にする
(1,2) から (2,2) へ移動
(2,2) から (3,2) へ移動
(3,2) から (3,3) へ移動

入力例2

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

出力例2

11