の大きさの迷路があります。
上から 行目、左から 列目のマスは文字 で与えられ、 は .
, #
のいずれかです。
.
は道であり、移動可能#
は壁であり、移動不可さめくんは 秒ごとに以下のいずれかの行動をします。
.
を選び、選んだマスに移動する #
を選び、選んだマスを壊して 道 .
にするさめくんが から に移動するのに必要な最短の時間を求めてください。
は .
, #
のいずれか
と は 道 .
である
答えを出力してください。
3 3 ..# ### #..
5
以下のような手順で 5 秒で移動できます
(1,1) から (1,2) へ移動 (2,2) の壁を壊して道にする (1,2) から (2,2) へ移動 (2,2) から (3,2) へ移動 (3,2) から (3,3) へ移動
5 5 .#..# #..#. ..#.. .#..# #..#.
11