2734. [郑州集训 2017]NOI模拟题2.2

【题目描述】

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

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

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

【输入格式】

第一行两个整数n,m，表示网格大小。

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

【输出格式】

一行一个正整数表示答案。

【样例输入】

3 2
#*
*#
##

【样例输出】

2

【提示】

对于20%的数据n,m<=5；

对于50%的数据满足n,m<=500；

对于100%的数据满足2<=n,m<=2000。