黑白棋子

题目描述

有一个$n$行$m$列的棋盘。棋盘的每个格子上要么是空，要么是一个黑色或白色的棋子。

我们现在将这个棋盘竖立起来，在游戏的任意时刻，这个棋盘都受到重力，满足不在最后一行的棋子下方都有棋子。

开始，棋盘上有一些棋子（但不一定是满的）。每一轮，玩家可以选择一个棋子$A$，然后将所有和棋子$A$在同一列的同一颜色连续段的棋子$B$全部消除（不包括$A$本身）。所有$A$和$B$在同一颜色连续段即$A$和$B$颜色相同，且该列在$A$和$B$之间棋子均与$A$同色。

若消除了至少一个棋子，那么消除成功，之后棋子$A$本身将反色（黑色变白色，白色变黑色），接着所有棋子向下掉落直到棋子落到最下方为止（棋子的相对顺序不变）；反之，如果没有棋子被消除，那么消除失败，棋盘不会有任何变化。

当所有棋子无法被消除时，游戏结束。

给定初始棋盘，请计算最少需要进行几轮消除才能使游戏结束。

输入格式

第一行包含两个正整数$n$，$m$，中间由一个空格隔开，表示棋盘为$n$行$m$列。

接下来$m$行，每行包含一个长度不超过$n$的非空字符串，依次描述每一列从下到上的棋子，字符串只含字符$0$和$1$，若第$i$个字符为$0$，表示该列从下往上第$i$个棋子为黑色，反之，若字符为$1$，表示棋子为白色。

输出格式

输出仅一行，包含一个整数，表示使游戏结束的最少消除轮数。

数据范围与提示

样例

4 3
10
1110
0100

5

说明

至少需要$5$轮消除，一种方案为依次选择：

• 第$2$列从下往上第$2$个棋子
• 第$3$列从下往上第$4$个棋子
• 第$2$列从下往上第$1$个棋子
• 第$3$列从下往上第$2$个棋子
• 第$3$列从下往上第$2$个棋子

注意最后两轮的消除是不一样的。

4 3
10
1110
0100

5

说明

初始时就无法消除任何棋子，故答案为$0$。

见eliminate.in 

见eliminate.ans