crack

题目描述

你有一个 $n$ 行 $m$ 列的网格，每个格子可以是坚硬的或是脆弱的。网格中恰有一个关键点，位于脆弱的格子上。

一个脆弱的格子可能会裂开，只需要同时不满足下列条件：

• 其左右两格子均存在（即在网格内）且没有裂开
• 其上下两格子均存在（即在网格内）且没有裂开

注意到裂开的操作是连锁反应，反应将一直进行直到稳定。

你希望关键点最终裂开，为此你可以将一些坚硬的格子敲成脆弱的，你想要知道最少敲几个格子可以满足要求。

输入格式

一行两个整数 $n,m$。

接下来 $n$ 行，每行 $m$ 个字符，描述这个网格。

字符共有三种。#表示坚硬的格子，+表示脆弱的格子，P表示关键点。

输出格式

一行一个整数表示答案。

样例输入

3 3
+#+
#P#
+#+

样例输出

2

数据范围

本题设有subtask。

对于全部数据，$1\leq n,m\leq 40$。

subtask1(20)，坚硬的格子个数不超过 $15$ 个

subtask2(30)，$1\leq n,m\leq 10$

subtask3(50)，无特殊限制。