Problem D: Blaster

Problem

なんと、あなたは洞窟の中に閉じ込められてしまいました！
壁が崩れたりでもしたのでしょうか、1つしかない出口にたどり着くまでには沢山の岩が邪魔をしています。

しかしなんと、あなたのすぐ隣に爆弾の自動販売機があることに気がつきました。
さらに、洞窟にはいくつかの「ブラスター」も落ちているようです。
この2つの道具を活用すれば、出口まで脱出できそうです。

アイテムの説明

洞窟内で使用できるアイテムとして、「爆弾」「ブラスター」の2種類があります。

• 爆弾は、使用することで1マス分の岩を破壊できるアイテムです。
  
• ブラスターは、使用することで自身の正面一直線にある岩を全て破壊することのできるアイテムです。
  

対象となる岩を破壊すると、岩は砕け散り「床」となります。
爆弾、ブラスターは使い切りで、各アイテムごとに使用できる回数はそれぞれ1回のみです。
また、ブラスターを使用することで、他のブラスターを破壊することはありません。

洞窟のフィールド

偶然手持ちにあったドローンを飛ばして、洞窟の様子を知ることが出来ました。

洞窟のフィールドが与えられます。
フィールドは以下のようなアスキーアートで与えらます。

_###
##B#
B##_

フィールドは、上下に $H$ マス、左右に $W$ マスの幅を持つ $H \times W$ のマスからなる長方形です。
$i$ 行 $j$ 列目のマスを $(i,j)$ と表します。

各マスには、床、壁、ブラスターのいずれかがあります。
ブラスターのマスには、床の上にちょうど1つのブラスターが落ちていることを示します。
なお、フィールドの外側は爆弾やブラスターでも破壊できない壁で囲まれています。
フィールドの外側に出ることは出来ません。

脱出までの行動

あなたは、以下の行動を任意の回数取ることが出来ます。

• 隣接するマスの、任意の床へ進む。
• 隣接するマスにある任意のブラスターを取得する。取得後、ブラスターを取得したマスは床となる。
• 隣接するマスにある岩を、爆弾を1つ消費して破壊する。
• 現在のマスから、上下左右好きな方向を向いて、所持しているブラスターを1つ使用する。

ここで、マス $(i,j)$ と $(k,l)$ が隣接するとは、 $|i-k|+|j-l|=1$ であることをいいます。
ブラスターは十分に軽いため、行動中いくつでも取得することが出来ます。
但し、アイテムの説明に記載してあるとおり、取得した個数分の回数しかブラスターを使用することは出来ないので、注意してください。

最初、マス $(1,1)$ にいます。
脱出とは、マス $(H,W)$ に到達することを言います。

ミッション

あなたは、爆弾の自動販売機から大量の爆弾を買えば問題なく脱出できることに気づきました。
幸い、爆弾の自動販売機には $10^{100}$ 個の在庫があり脱出するには十分そうです。
しかし、爆弾は非常に高価であるためあまり沢山買いたくありません。
手に入れた洞窟の様子から、脱出するには最小でいくつの爆弾を買う必要があるか、知りたくなりました。

Input

入力は以下の形式で与えられる。

$H$ $W$
$c_{1,1}$$\cdots$$c_{1,W}$
$\vdots$
$c_{H,1}$$\cdots$$c_{H,W}$

1行目に $H,W$ が空白区切りに与えられます。
2行目から、続く $H$ 行にフィールドの情報がアスキーアートで与えられます。

フィールドの情報は、それぞれの文字ごとに以下の意味を持ちます。

• $c_{i,j}$ が '#' のとき、 $(i,j)$ に岩があることを示す。
• $c_{i,j}$ が '_' のとき、 $(i,j)$ に床があることを示す。
• $c_{i,j}$ が 'B' のとき、 $(i,j)$ にブラスターがちょうど1つあることを示す。

Constraints

入力は以下の条件を満たす。

• $2 \leq H,W \leq 1000 $
• $H,W$ は整数である
• $c_{1,1},c_{H,W}$ は、必ず'_'である。

Output

1行に脱出に必要な爆弾の数を出力せよ。

Sample Input 1

8 5
_###_
_#_B#
_####
____#
###_#
#####
###_#
####_

Sample Output 1

1

この場合の脱出方法は、

• マス $(3,4)$ にある岩を爆弾で破壊する
• マス $(2,4)$ にあるブラスターを取得する
• マス $(2,4)$ で下方向にブラスターを使用する
• 脱出！

このように、爆弾 $1$ つで脱出することが出来ます。
なお、ブラスターを使用した直後のフィールドは、以下のようになっています。

_###_
_#__#
_##_#
____#
###_#
###_#
###_#
###__

Sample Input 2

5 5
_____
_____
_____
_____
_____

Sample Output 2

0

邪魔する岩もブラスターもありません。目の錯覚だったのでしょうか。
爆弾を一つも買うことなく、脱出できる場合もあります。

Sample Input 3

4 5
_####
##B##
_####
_###_

Sample Output 3

2

マス $(2,1),(2,2)$ にある岩を破壊すれば、爆弾 $2$ つだけで脱出可能です。

Sample Input 4

4 5
_#B##
#####
##B##
####_

Sample Output 4

1