A6034 | $「2017 山东二轮集训 Day2」第二题$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

小火车觉得对生活已经没有什么好留恋的了，于是决定前往二次元去寻找真爱。 既然去了二次元就得玩玩二次元的游戏了，游戏当然是在一个二维网格中展开的，网格大小是 $ n \times m $ 的，某些格子是好的，其余的则是不好的。每次你可以选择最底层（也就是第 $ n $ 层）的某两个相邻的列，并消掉最底下的至多三个格子，并且这两列都得有格子被消掉（也就是 L 型或者反着的 L 型），消掉格子以后上面的格子会掉落下来。当然最上面的空位会用不好的格子填满。 小火车想得到所有的好格子送给妹子，请问至少得消多少次呢？

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

一行一个整数表示答案。

输入 #1

3 2
#*
*#
##

输出 #1

C++ 编辑器

输入

输出