#P1006. 抱团取暖

抱团取暖

题目背景

冬天来了,即使肥肥的绵羊们也需要挤在一起取暖。

404 Not Found

题目描述

在一片冰天雪地中,有几群绵羊正在抱团取暖。但是,很不幸的是,如果和一只绵羊抱在一起的不到 2 只活着的绵羊,那么这只绵羊就会被冻死。

其中绵羊 # 抱在一起的绵羊 * 可以在如下四个位置:

 *
*#*
 *

为了准备足够的坑来埋死去的绵羊,绿绵羊想知道有多少只绵羊会活下来。

格式

输入格式

一行,两个整数 nnmm,表示地图的大小。

接下来 nn 行,每行 mm 个字符。. 表示地面,# 表示绵羊。

输出格式

一行,一个整数,表示有多少绵羊会活下来。

数据样例

4 4
####
....
####
###.
6

样例1解释

根据题目描述,地图会先变成这样(x 表示尸体):

x##x
....
###x
###.

此时又有一些绵羊冻死,形成连锁反应。最终活下来的绵羊:

xxxx
....
###x
###.

数据规模与约定

对于 30%30\% 的数据,1n,m501\leq n,m\leq 50

对于 60%60\% 的数据,保证数据由随机数程序生成。

对于 100%100\% 的数据,1n,m5×1031\leq n,m\leq 5 \times 10^3