Problem Description

In a certain area of the Arctic Sea, there is a grid of ice floes arranged in \( H \) rows and \( W \) columns. Let the square at the \( i \)-th row and \( j \)-th column be denoted as square \( (i,j) \). The ice floes floating there are either thin ice or icebergs, and exactly one square of thin ice is inhabited by a penguin. Additionally, there is no ice floating outside the \( H \) rows and \( W \) columns grid.

The ice floe at square \( (i,j) \) is represented by the character \( S_{i,j} \). \( S_{i,j} \) can be +, #, or P, each representing the following:

• +: Thin ice is floating.
• #: An iceberg is floating.
• P: Thin ice is floating, and a penguin lives there.

In summer, unstable thin ice that is not surrounded by icebergs or other stable thin ice will start to collapse one after another. Specifically, the thin ice at square \( (i,j) \) will collapse if it does not meet both of the following conditions:

• Both squares \( (i-1,j) \) and \( (i+1,j) \) contain an iceberg or non-collapsed thin ice.
• Both squares \( (i,j-1) \) and \( (i,j+1) \) contain an iceberg or non-collapsed thin ice.

The collapse can occur in a chain reaction. Icebergs, however, do not collapse.

Now, a mischievous traveler has come and plans to tamper with the thin ice where the penguin lives so that it will collapse in summer. The traveler can change icebergs into thin ice by hammering them. What is the minimum number of icebergs that the traveler needs to change into thin ice to achieve this?

Input Format

The input is given from the standard input in the following format:

\( 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} \)

Output Format

Output the minimum number of icebergs that need to be changed into thin ice to ensure the thin ice where the penguin lives collapses in summer.

Sample Input and Output

Sample Input #1

3 3
+#+
#P#
+#+

Sample Output #1

2

Sample Input #2

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

Sample Output #2

1

Sample Input #3

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

Sample Output #3

151

Sample Input #4

1 1
P

Sample Output #4

0

Notes/Hints

Constraints

• \( 1 \leq H, W \leq 40 \)
• \( S_{i,j} \) is either +, #, or P.
• \( S \) contains exactly one P.

见题面 Input 部分

见题面 Output 部分