1015: 消除之王

时间限制: C/C++ 1 s      Java/Python 3 s      内存限制: 128 MB      答案正确: 16 / 58     

题目描述

 自从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个格子。

输入

输入的第一行是T,代表的测试数据组数
每组数据的开始是n,m(1<=n<=4,1<=m<=4).代表了行数和列数
然后是n行,每行包括m个字符 (只为1或0)。

输出

输出一行表示最小的格子数

样例输入

2
1 1
1
4 4
1010
0101
1010
0101

样例输出

1
16

提示

来源

标签

#校赛  

提交代码






© 2019 JustOJ     中文  English  | l.jiang.1024@gmail.com | Docs | System Info | Telegram Group | Telegram Channel