問題文


の大きさの迷路があります。
上から 行目、左から 列目のマスは文字 で与えられ、. , # のいずれかです。

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

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

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

さめくんが から に移動するのに必要な最短の時間を求めてください。

制約



. , # のいずれか
は 道 . である

入力





出力


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

入力例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

Submit


Go (1.14)