裁玻璃-j9国际集团直营

1038: 裁玻璃

时间限制: 1000 ms  内存限制: 128 MB
提交: 238  解决: 46
[提交][状态][讨论版]

题目描述

张老板的玻璃店开张了，生意火爆。今天，隔壁玻璃店的刘老板拿来一块玻璃，意在刁难张老板。刘老板说：“我这块玻璃是由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

提示

来源

2014西电ACM校赛现场赛

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