なんと、あなたは洞窟の中に閉じ込められてしまいました！
壁が崩れたりでもしたのでしょうか、1つしかない出口にたどり着くまでには沢山の岩が邪魔をしています。
しかしなんと、あなたのすぐ隣に爆弾の自動販売機があることに気がつきました。
さらに、洞窟にはいくつかの「ブラスター」も落ちているようです。
この2つの道具を活用すれば、出口まで脱出できそうです。
洞窟内で使用できるアイテムとして、「爆弾」「ブラスター」の2種類があります。
対象となる岩を破壊すると、岩は砕け散り「床」となります。
爆弾、ブラスターは使い切りで、各アイテムごとに使用できる回数はそれぞれ1回のみです。
また、ブラスターを使用することで、他のブラスターを破壊することはありません。
偶然手持ちにあったドローンを飛ばして、洞窟の様子を知ることが出来ました。
洞窟のフィールドが与えられます。
フィールドは以下のようなアスキーアートで与えらます。
_### ##B# B##_
フィールドは、上下に $H$ マス、左右に $W$ マスの幅を持つ $H \times W$ のマスからなる長方形です。
$i$ 行 $j$ 列目のマスを $(i,j)$ と表します。
各マスには、床、壁、ブラスターのいずれかがあります。
ブラスターのマスには、床の上にちょうど1つのブラスターが落ちていることを示します。
なお、フィールドの外側は爆弾やブラスターでも破壊できない壁で囲まれています。
フィールドの外側に出ることは出来ません。
あなたは、以下の行動を任意の回数取ることが出来ます。
ここで、マス $(i,j)$ と $(k,l)$ が隣接するとは、 $|i-k|+|j-l|=1$ であることをいいます。
ブラスターは十分に軽いため、行動中いくつでも取得することが出来ます。
但し、アイテムの説明に記載してあるとおり、取得した個数分の回数しかブラスターを使用することは出来ないので、注意してください。
最初、マス $(1,1)$ にいます。
脱出とは、マス $(H,W)$ に到達することを言います。
あなたは、爆弾の自動販売機から大量の爆弾を買えば問題なく脱出できることに気づきました。
幸い、爆弾の自動販売機には $10^{100}$ 個の在庫があり脱出するには十分そうです。
しかし、爆弾は非常に高価であるためあまり沢山買いたくありません。
手に入れた洞窟の様子から、脱出するには最小でいくつの爆弾を買う必要があるか、知りたくなりました。
入力は以下の形式で与えられる。
$H$ $W$
$c_{1,1}$$\cdots$$c_{1,W}$
$\vdots$
$c_{H,1}$$\cdots$$c_{H,W}$
1行目に $H,W$ が空白区切りに与えられます。
2行目から、続く $H$ 行にフィールドの情報がアスキーアートで与えられます。
フィールドの情報は、それぞれの文字ごとに以下の意味を持ちます。
入力は以下の条件を満たす。
1行に脱出に必要な爆弾の数を出力せよ。
8 5 _###_ _#_B# _#### ____# ###_# ##### ###_# ####_
1
この場合の脱出方法は、
このように、爆弾 $1$ つで脱出することが出来ます。
なお、ブラスターを使用した直後のフィールドは、以下のようになっています。
_###_ _#__# _##_# ____# ###_# ###_# ###_# ###__
5 5 _____ _____ _____ _____ _____
0
邪魔する岩もブラスターもありません。目の錯覚だったのでしょうか。
爆弾を一つも買うことなく、脱出できる場合もあります。
4 5 _#### ##B## _#### _###_
2
マス $(2,1),(2,2)$ にある岩を破壊すれば、爆弾 $2$ つだけで脱出可能です。
4 5 _#B## ##### ##B## ####_
1