问题描述

在北冰洋的某个地方，海面上漂浮着 $H$ 行 $W$ 列的冰块。我们将这片区域看作一个网格，并将第 $i$ 行第 $j$ 列的方格表示为 Square $(i,j)$。每个方格中漂浮着的冰块要么是薄冰，要么是冰山，而且有一只企鹅居住在其中一个包含薄冰的方格中。在网格范围外没有冰块。

Square $(i,j)$ 中的冰块用字符 $S_{i,j}$ 表示。 $S_{i,j}$ 是 +、# 或 P，分别表示以下情况：

• +：被薄冰占据。
• #：被冰山占据。
• P：被薄冰占据。企鹅住在这里。

当夏天来临时，不稳定的薄冰会相继崩溃。正式地说，当 Square $(i,j)$ 不满足以下条件之一时，其中的薄冰就会崩溃：

• Square $(i-1,j)$ 和 Square $(i+1,j)$ 都被冰山或未坍塌的薄冰占据。
• Square $(i,j-1)$ 和 Square $(i,j+1)$ 都被冰山或未坍塌的薄冰占据。

当发生一次崩溃时，可能会引发其他崩溃。请注意，冰山不会崩溃。

现在，有个调皮的游客来到这里。为了在夏天来临时使企鹅所居住的薄冰坍塌，他将做一些手脚。他可以用大锤砸碎一座冰山，使其变成薄冰。他至少需要砸碎多少座冰山？

约束条件

• $1 \leq H,W \leq 40$
• $S_{i,j}$ 是 +、# 或 P。
• $S$ 中恰好包含一个 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}$

输出

打印需要砸碎的冰山的最小数量，以便在夏天来临时导致企鹅所处的薄冰坍塌。

---

示例输入 1

3 3
+#+
#P#
+#+

示例输出 1

2

例如，当右边和下方的冰山变为薄冰时，崩溃如下所示：

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

---

示例输入 2

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

示例输出 2

1

---

示例输入 3

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

示例输出 3

151

---

示例输入 4

1 1
P

示例输出 4

0