欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~

问题 1038. -- 裁玻璃

1038: 裁玻璃

时间限制: 1 Sec  内存限制: 128 MB
提交: 146  解决: 16
[提交][状态][讨论版]

题目描述

张老板的玻璃店开张了,生意火爆。今天,隔壁玻璃店的刘老板拿来一块玻璃,意在刁难张老板。刘老板说:“我这块玻璃是由N(行)*M(列)小正方形玻璃拼成的,但是其中有一些玻璃坏了,我希望你现在把它裁成尽量多的2*2的小玻璃,而且这些小玻璃都不能有坏的地方。如果你裁出来的块数不是最多的,我就把你赶出建材市场。”
现在,张老板来拜托你帮他解决这个问题,聪明的你可以告诉张老板,最多能裁出多少块2*2的小玻璃吗?

输入

有多组输入数据,第一行为一个数字T,代表有T组输入数据 (0<T<=30)。
接下来为T组数据,每组数据的第一行为两个正整数N和M(1<=N<=10,1<=M<=10),表示玻璃的大小,接下来的N行、每行M个数字(0或1)表示玻璃中每个位置的状态,0表示这个位置是坏的,1表示这个位置是好的。

输出

一共T行。
对于每组数据,输出一个整数,表示最多的2*2小玻璃块数。

样例输入

2
2 3
1 1 1
1 1 1
4 4
0 0 1 1
0 1 1 1
1 1 1 1
1 1 1 1

样例输出

1
3

提示

来源

[提交][状态][讨论版]