配点 : $1600$ 点

問題文

北極海のとある場所に $H$ 行 $W$ 列のマス目状に氷が浮かんでいます。 $i$ 行目 $j$ 列目のマスをマス $(i,j)$ と表すことにします。 浮かんでいる氷は薄氷または氷山であり、薄氷のマスのうちちょうど $1$ マスにはペンギンが住んでいます。 また、$H$ 行 $W$ 列のマス目の外には氷は浮かんでいません。

マス $(i,j)$ に浮かんでいる氷は文字 $S_{i,j}$ で表されます。 $S_{i,j}$ は +、#、P のいずれかであり、それぞれ以下のようなことを表しています。

• +：薄氷が浮かんでいる。
• #：氷山が浮かんでいる。
• P：薄氷が浮かんでおり、ペンギンが住んでいる。

夏になると、氷に挟まれていない不安定な薄氷は次々に崩落していってしまいます。 つまり、マス $(i,j)$ の薄氷が以下の条件をいずれも満たしていないとき、その薄氷は崩落してしまいます。

• マス $(i-1,j)$ とマス $(i+1,j)$ の両方に氷山または崩落していない薄氷が存在する。
• マス $(i,j-1)$ とマス $(i,j+1)$ の両方に氷山または崩落していない薄氷が存在する。

崩落は連鎖的に発生することもあります。 また、氷山は崩落しません。

さて、ここに悪い旅人がやってきてペンギンの住んでいる薄氷が夏になると崩落するように細工をしようと考えました。 旅人はハンマーで氷山を叩いて薄氷に変えることができます。 旅人は最小でいくつの氷山を薄氷に変えれば良いでしょうか？

制約

• $1 \leq H,W \leq 40$
• $S_{i,j}$ は +、#、P のいずれかである。
• $S$ はちょうど $1$ つだけ P を含む。

入力

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

$H$ $W$

$S_{1,1}$$S_{1,2}$$...$$S_{1,W}$

$S_{2,1}$$S_{2,2}$$...$$S_{2,W}$

$:$

$S_{H,1}$$S_{H,2}$$...$$S_{H,W}$

出力

ペンギンの住んでいる薄氷が夏になると崩落するようにするために薄氷に変える必要のある氷山の個数の最小値を出力せよ。

3 3
+#+
#P#
+#+

2

例えば右と下の氷山を薄氷に変えると以下のように薄氷が崩落していきます。

+#+    .#.    .#.    .#.
#P+ -> #P+ -> #P. -> #..
+++    .+.    ...    ...

6 6
#+++++
+++#++
#+++++
+++P+#
+##+++
++++#+

1

40 40
#++#+++++#+#+#+##+++++++##+#+++#++##++##
+##++++++++++#+###+##++++#+++++++++#++##
+++#+++++#++#++####+++#+#+###+++##+++#++
+++#+######++##+#+##+#+++#+++++++++#++#+
+++##+#+#++#+++#++++##+++++++++#++#+#+#+
#++#+++#+#++++##+#+#+++##+#+##+#++++##++
++#+##+++#++####+#++##++#+++#+#+#++++#++
+#+###++++++##++++++#++##+#####++#++##++
##+##+#+++#+#+##++#+###+######++++#+###+
+++#+++##+#####+#+#++++#+#+++++#+##++##+
#+++#+##+++++++#++#++++++++++###+#++#+#+
##+++##++#+++++#++++#++#+##++#+#+#++##+#
##+++#+###+++++##++#+#+++####+#+++++#+++
+++#++#++#+++++++++#++###++++++++###+##+
++#+++#++++++#####++##++#+++#+++++#++++#
++#++#+##++++#####+###+++####+#+#+######
++++++##+++++##+++++#++###++#++##+++++++
+#++++##++++++#++++#+#++++#++++##+++##+#
+++++++#+#++##+##+#+++++++###+###++##+++
++++++#++###+#+#+++##+#++++++#++#+#++#+#
##+##++++++#+++++#++#+#++##+++#+#+++##+#
#+++#+#+##+#+##++#P#++#++++++##++#+#++##
#+++#++##+##+#++++#++#++##++++++#+#+#+++
++++####+#++#####+++#+###+#++###++++#++#
#+#++####++##++#+#+#+##+#+#+##++++##++#+
+###+###+#+##+++#++++++#+#++++###+#+++++
+++#+++++#+++#+++++##++++++++###++#+#+++
+#+#++#+#++++++###+#++##+#+##+##+#+#####
#++++++++#+#+###+######++#++#+++++++++++
##+++##+#+#++#++#++#++++++#++##+#+#++###
+#+#+#+++++++#+++++++######+##++#++##+##
++#+++#+###+#++###+++#+++#+#++++#+###+++
#+#+###++#+#####+++++#+####++#++#+###+++
+#+##+#++#++##+++++++######++#++++++++++
+####+#+#+++++##+#+#++#+#++#+++##++++#+#
#++##++#+#+++++##+#++++####+++++###+#+#+
##+#++#++#+##+#+#++##++###+###+#+++++##+
##++###+###+#+#++#++#########+++###+#+##
+++#+++#++++++++++#+#+++#++#++###+####+#
++##+###+++++++##+++++#++#++++++++++++++

151

1 1
P

0