#6104. 「2017 山东二轮集训 Day2」第二题

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小火车觉得对生活已经没有什么好留恋的了,于是决定前往二次元去寻找真爱。

既然去了二次元就得玩玩二次元的游戏了,游戏当然是在一个二维网格中展开的,网格大小是 n \times m 的,某些格子是好的,其余的则是不好的。每次你可以选择最底层(也就是第 n 层)的某两个相邻的列,并消掉最底下的至多三个格子,并且这两列都得有格子被消掉(也就是 L 型或者反着的 L 型),消掉格子以后上面的格子会掉落下来。当然最上面的空位会用不好的格子填满。

小火车想得到所有的好格子送给妹子,请问至少得消多少次呢?

输入格式

第一行两个整数 n, m ,表示网格大小。
接下来 n 行每行一个长度为 m 的字符串,表示这个网格,如果为 * 则是好格子,为 # 就不是。

输出格式

一行一个整数表示答案。

样例

样例输入

3 2
#*
*#
##

样例输出

2

数据范围与提示

对于 20\% 的数据 n, m \leq 5
对于 50\% 的数据满足 n, m \leq 500
对于 100\% 的数据满足 2 \leq n, m \leq 2000