← 返回题目列表

Codeforces · 1864/D

D. 矩阵级联

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

有一个大小为 $$$n \times n$$$ 的矩阵,由 0 和 1 组成。行从上到下编号为 $$$1$$$ 到 $$$n$$$,列从左到右编号为 $$$1$$$ 到 $$$n$$$。第 $$$x$$$ 行和第 $$$y$$$ 列交叉处的单元格表示为 $$$(x, y)$$$。

AquaMoon 想要将矩阵的所有元素都变为 0。她可以一步执行以下操作:

- 选择任意单元格,设为 $$$(i, j)$$$,然后反转 $$$(i, j)$$$ 中的元素,并反转单元格 $$$(x, y)$$$ 中的所有元素,对于 $$$x > i$$$ 和 $$$x - i \ge \left|y - j\right|$$$。反转一个值意味着将其更改为相反的值:0 变为 1,1 变为 0。

帮助 AquaMoon 确定将矩阵的所有元素变为 0 所需执行的最少步骤数。我们可以证明答案总是存在的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3000$$$)。

以下 $$$n$$$ 行中的第 $$$i$$$ 包含仅由字符 0 和 1 组成的二进制字符串,长度为 $$$n$$$。

保证所有测试用例的$$$n^2$$$总和不超过$$$9\,000\,000$$$。

输出

对于每个测试用例,打印最小步骤数。

示例

输入 #1

3
5
00100
01110
11111
11111
11111
3
100
110
110
6
010101
111101
011110
000000
111010
001110

输出 #1

1
2
15

注意

在第一个测试用例中,我们可以使用以下方案:

1. 对单元格$$$(1, 3)$$$执行操作。

显然,初始矩阵的元素不全为0,因此至少需要进行一次运算。因此,$$$1$$$ 就是答案。

在第二个测试用例中,我们使用以下方案:

1. 对单元格$$$(3, 3)$$$执行操作;
2. 对单元格$$$(1, 1)$$$执行操作。

可以看出,$$$0$$$或$$$1$$$步中没有办法将所有元素都转换为0,所以答案正是$$$2$$$。