自从shoushou同学下了 popstar(http://www.pc6.com/azyx/78703.html)这个游戏之后便疯狂的玩了起来。 但是因为shoushou的IQ比较低,每次都拿不到高分,shoushou很生气,你能帮帮他吗?
为了将问题简化,题目将给出大小为n*m (1<=n<=4,1<=m<=4)的只含0,1的矩阵。你每次可以选择一个区域(连续不间断),如果这个区域所含的格子数大于1,而且全部为0或者全部为1的时候就可以将这块区域消除。(注意:而且与这个区域相连通的同颜色的格子也同样会消除! )之后如果剩下来的任意一个格子的下方为空的时候,就会向下移动直到到达最底端或下方出现其他格子。 也就是说每个格子都会下落! 需要注意的是:格子只会向下移动而不会左右移动!
举个例子:
给出了一个4*4的矩阵
0011
0000
0011
0000
- . - - . - - . -- . -- . -- . -- . -- . -- . -- . -- . -- . -- . -- . --- . --- . --- . --- . --- . -
当我们选择
00
0000
00
0000
这个区域消除的话,就会变成
....
....
..11
..11 ('.'代表空)
- . - - . - - . -- . -- . -- . -- . -- . -- . -- . -- . -- . -- . -- . --- . --- . --- . --- . --- . -
现在问题来了,你可以进行任意多次的这种消除操作,求所留下来的最小格子数是多少?
显然前面给出的例子可以全部消除完,也就是还剩下0个格子。