AT_cf17_final_h.Poor Penguin

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在北冰洋, 海上漂浮着 $H$ 行 $W$ 列的冰块. 我们将该区域视为网格, 并将第 $i$ 行和第 $j$ 列的方格表示为 $Square(i,j)$ . 漂浮在每个方格中的冰块不是薄冰就是厚冰. 正方形网格外没有冰块.

$Square(i,j)$ 处的冰块可以用以下三种字符表示:

+ 此方格是薄冰.
# 此方格是厚冰.
P 此方格是企鹅所在地, 为薄冰.

(译者:北冰洋-企鹅?????)

夏天一到, 因温度上升和薄冰的不稳定性, 薄冰将会一个接一个的融化消失. 我们定义, $Square(i,j)$ 处的薄冰在不满足以下任意一种情况时就会融化:

$Square(i-1,j)$ 和 $Square(i+1,j)$ 都有冰块.
$Square(i,j-1)$ 和 $Square(i,j+1)$ 都有冰块.

现在, 一个不怀好意的人来到了这里. 他可以用锤子砸厚冰, 使其变为薄冰. 请问, 他至少要砸多少块厚冰, 才能使企鹅所在处的冰块融化消失?

输入格式

第一行两个正整数 $H$ 和 $W$ , 含义如题意所示.

接下来一个 $H$ 行 $W$ 列的字符矩阵表示方格图, 有且只有题意所给的三个字符.

输出格式

一行一个数表示最少块数.

输入输出样例

输入#1
```
3 3
+#+
#P#
+#+
```
输出#1
```
2
```

输入#2

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

输出#2

输入#3

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

输出#3

输入#4
```
1 1
P
```
输出#4
```
0
```

说明/提示

对于 100% 的数据, $1 \le H,W \le 40$ .

输入解题思路，AI测评打分。不知道怎么写?

首页