← 返回题目列表

Codeforces · 1720/C

C. 角落

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 行和 $$$m$$$ 列组成的矩阵。该矩阵的每个单元格包含 $$$0$$$ 或 $$$1$$$。

我们将一个大小为 $$$2 \times 2$$$ 且没有角单元的正方形称为 L 形图形。在一项操作中,您可以获取一个 L 形图形,其中至少一个单元格包含 $$$1$$$,并将其中的所有数字替换为零。

找出可以对给定矩阵执行的最大运算次数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 500$$$) — 测试用例的数量。然后遵循每个测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n, m \leq 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

注意

在第一个测试用例中,最佳操作顺序之一如下(粗体字体显示执行操作的 L 形图形):

- 执行任何操作之前的矩阵:101111011110
- 执行 $$$1$$$ 操作后的矩阵:100101011110
- 执行 $$$2$$$ 操作后的矩阵:100100011110
- 执行 $$$3$$$ 操作后的矩阵:100100010110
- 执行 $$$4$$$ 操作后的矩阵:100000010110
- 执行 $$$5$$$ 操作后的矩阵:100000010100
- 执行 $$$6$$$ 操作后的矩阵:100000000100
- 执行 $$$7$$$ 操作后的矩阵:000000000100
- 执行 $$$8$$$ 操作后的矩阵:000000000000

在示例的第三个测试用例中,我们无法执行任何操作,因为矩阵不包含任何操作。

在第四个测试用例中,我们在第一次操作中选择哪个 L 形图形并不重要。我们将永远只剩下一个。因此我们将执行 $$$2$$$ 操作。