CF1720C Corners

给定一个包含 $n$ 行 $m$ 列的矩阵。矩阵中的每个单元格包含 $0$ 或 $1$。 我们将一个 $2 \times 2$ 的正方形去掉一个角的部分称为“L 形”图形。在一次操作中，你可以选择一个“L 形”图形（该图形中至少有一个单元格为 $1$），并将该图形内的所有数字都替换为 $0$。 请你求出对于给定的矩阵，最多可以进行多少次这样的操作。

第一行包含一个整数 $t$（$1 \leq t \leq 500$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \leq n, m \leq 500$），表示矩阵的大小。 接下来的 $n$ 行，每行是一个长度为 $m$ 的二进制字符串，描述了矩阵的内容。 保证所有测试用例中 $n$ 的和与 $m$ 的和不超过 $1000$。

对于每个测试用例，输出一个整数，表示最多可以进行多少次操作。

在第一个测试用例中，一种最优的操作序列如下（加粗部分表示本次操作选择的 L 形图形）： - 操作前的矩阵： 101111011110 - 第 $1$ 次操作后的矩阵： 100101011110 - 第 $2$ 次操作后的矩阵： 100100011110 - 第 $3$ 次操作后的矩阵： 100100010110 - 第 $4$ 次操作后的矩阵： 100000010110 - 第 $5$ 次操作后的矩阵： 100000010100 - 第 $6$ 次操作后的矩阵： 100000000100 - 第 $7$ 次操作后的矩阵： 000000000100 - 第 $8$ 次操作后的矩阵： 000000000000 在样例的第三个测试用例中，矩阵中没有任何 $1$，因此无法进行任何操作。 在样例的第四个测试用例中，无论第一次选择哪个 L 形图形，最终都会剩下一个 $1$，因此最多可以进行 $2$ 次操作。 由 ChatGPT 4.1 翻译