← 返回题目列表

AtCoder · cf17_final_h

H. 可怜的企鹅

中文机器翻译题面 查看原题

分数: 1600 点

问题陈述

在北冰洋的某些地方,有 H 行和 W 海面上漂浮着冰柱。 我们把这个区域看成一个网格,并用它来表示正方形 i第行和 j第列为正方形 (i,j)。 每个方格中漂浮的冰块要么是薄冰,要么是冰山,一只企鹅生活在其中一个包含薄冰的方格中。 网格外没有漂浮的冰块。

广场的冰块 (i,j) 由字符表示 S_{i,j}. S_{i,j} is +, # or P,每个含义如下:

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

当夏天到来时,不稳定的薄冰,不是由一些冰块夹住的,会相继崩塌。 正式来说,Square 的情况如履薄冰 (i,j) 当不满足以下任一条件时将崩溃:

  • 两个正方形 (i-1,j) 和广场 (i+1,j) 被冰山或未塌陷的薄冰占据。
  • 两个正方形 (i,j-1) 和广场 (i,j+1) 被冰山或未塌陷的薄冰占据。

当崩溃发生时,可能会导致另一次崩溃。请注意,冰山不会倒塌。

现在,一位淘气的游客来到这里。他会做一些工作,以便当夏天到来时,企鹅居住的薄冰会崩塌。 他可以用锤子砸碎冰山,将其变成薄冰。 他至少需要砸碎多少冰山?

约束

  • 1 \leq H,W \leq 40
  • S_{i,j} is +, # or 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