Corners

题意翻译

有一个由 0 和 1 组成的矩阵。 每次操作可以选择一个 $2\times 2$ 的子矩阵，在这个子矩阵中选择一个 L 形，将这个 L 形里的 3 个数变成 $0$，注意，这个 L 形至少含有一个 1，你想最大化操作个数，问最多操作多少次。

题目描述

You are given a matrix consisting of $ n $ rows and $ m $ columns. Each cell of this matrix contains $ 0 $ or $ 1 $ . Let's call a square of size $ 2 \times 2 $ without one corner cell an L-shape figure. In one operation you can take one L-shape figure, with at least one cell containing $ 1 $ and replace all numbers in it with zeroes. Find the maximum number of operations that you can do with the given matrix.

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \leq t \leq 500 $ ) — the number of test cases. Then follow the descriptions of each test case. The first line of each test case contains two integers $ n $ and $ m $ ( $ 2 \leq n, m \leq 500 $ ) — the size of the matrix. Each of the following $ n $ lines contains a binary string of length $ m $ — the description of the matrix. It is guaranteed that the sum of $ n $ and the sum of $ m $ over all test cases does not exceed $ 1000 $ .

输出格式

For each test case output the maximum number of operations you can do with the given matrix.

输入输出样例

输入样例 #1

4
4 3
101
111
011
110
3 4
1110
0111
0111
2 2
00
00
2 2
11
11

输出样例 #1

8
9
0
2

说明

In the first testcase one of the optimal sequences of operations is the following (bold font shows l-shape figure on which operation was performed): - Matrix before any operation was performed: 101111011110 - Matrix after $ 1 $ operation was performed: 100101011110 - Matrix after $ 2 $ operations were performed: 100100011110 - Matrix after $ 3 $ operations were performed: 100100010110 - Matrix after $ 4 $ operations were performed: 100000010110 - Matrix after $ 5 $ operations were performed: 100000010100 - Matrix after $ 6 $ operations were performed: 100000000100 - Matrix after $ 7 $ operations were performed: 000000000100 - Matrix after $ 8 $ operations were performed: 000000000000 In the third testcase from the sample we can not perform any operation because the matrix doesn't contain any ones. In the fourth testcase it does not matter which L-shape figure we pick in our first operation. We will always be left with single one. So we will perform $ 2 $ operations.

题目大意：
给定一个由0和1组成的矩阵。每次操作可以选择一个2×2的子矩阵，在这个子矩阵中选择一个L形，将这个L形里的3个数变成0，注意，这个L形至少含有一个1，你想最大化操作个数，问最多操作多少次。

输入输出数据格式：
输入格式：
第一行包含一个整数t（1≤t≤500）——测试用例的数量。然后是每个测试用例的描述。
每个测试用例的第一行包含两个整数n和m（2≤n，m≤500）——矩阵的大小。
接下来的n行每行包含一个长度为m的二进制字符串——矩阵的描述。
保证所有测试用例的n和m的总和不超过1000。

输出格式：
对于每个测试用例输出给定矩阵可以进行的最大操作数。

输入输出样例：
输入样例 #1
```
4
4 3
101
111
011
110
3 4
1110
0111
0111
2 2
00
00
2 2
11
11
```
输出样例 #1
```
8
9
0
2
```题目大意： 给定一个由0和1组成的矩阵。每次操作可以选择一个2×2的子矩阵，在这个子矩阵中选择一个L形，将这个L形里的3个数变成0，注意，这个L形至少含有一个1，你想最大化操作个数，问最多操作多少次。 输入输出数据格式： 输入格式： 第一行包含一个整数t（1≤t≤500）——测试用例的数量。然后是每个测试用例的描述。 每个测试用例的第一行包含两个整数n和m（2≤n，m≤500）——矩阵的大小。 接下来的n行每行包含一个长度为m的二进制字符串——矩阵的描述。 保证所有测试用例的n和m的总和不超过1000。 输出格式： 对于每个测试用例输出给定矩阵可以进行的最大操作数。 输入输出样例： 输入样例 #1 ``` 4 4 3 101 111 011 110 3 4 1110 0111 0111 2 2 00 00 2 2 11 11 ``` 输出样例 #1 ``` 8 9 0 2 ```