← 返回题目列表

Codeforces · 1660/E

E. 矩阵和移位

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

给定一个二进制矩阵 $$$A$$$,大小为 $$$n \times n$$$。行从上到下从 $$$1$$$ 到 $$$n$$$ 编号,列从左到右从 $$$1$$$ 到 $$$n$$$ 编号。位于行 $$$i$$$ 和列 $$$j$$$ 相交处的元素称为 $$$A_{ij}$$$。考虑一组 $$$4$$$ 操作:

1. 循环向上移动所有行。索引为 $$$i$$$ 的行将替换行 $$$i-1$$$ ($$$2 \le i \le n$$$),索引为 $$$1$$$ 的行将替换行 $$$n$$$。
2. 循环下移所有行。索引为 $$$i$$$ 的行将替换行 $$$i+1$$$ ($$$1 \le i \le n - 1$$$),索引为 $$$n$$$ 的行将替换行 $$$1$$$。
3. 循环将所有列向左移动。索引为 $$$j$$$ 的列将代替列 $$$j-1$$$ ($$$2 \le j \le n$$$),索引为 $$$1$$$ 的列将代替列 $$$n$$$。
4. 循环右移所有列。索引为 $$$j$$$ 的列将代替列 $$$j+1$$$ ($$$1 \le j \le n - 1$$$),索引为 $$$n$$$ 的列将代替列 $$$1$$$。

$$$3 \times 3$$$ 矩阵显示在左侧,在对其应用 $$$3$$$-rd 运算之前,右侧显示在应用 $$$3$$$-rd 运算之后。

您可以对矩阵执行任意(可能为零)次数的运算;这些操作可以按任何顺序执行。

之后,您可以执行任意(可能为零)数量的新异或运算:

- 选择任意元素 $$$A_{ij}$$$ 并为其分配新值 $$$A_{ij} \oplus 1$$$。换句话说,$$$(A_{ij} + 1) \bmod 2$$$ 的值必须写入元素$$$A_{ij}$$$。

此异或运算的每次应用都会花费一个树节。请注意,$$$4$$$ 移位操作是免费的。这些 $$$4$$$ 操作只能在执行异或操作之前执行。

输出使 $$$A$$$ 矩阵统一所需的最小节数。酉矩阵是主对角线上有 1 且其余元素为零的矩阵(即,如果 $$$i = j$$$,则 $$$A_{ij} = 1$$$,否则 $$$A_{ij} = 0$$$)。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中的测试用例数量。

测试用例的描述如下。在每个测试用例之前,在输入中写入一个空行。

每个测试用例的第一行包含一个数字 $$$n$$$ ($$$1 \le n \le 2000$$$)

接下来是 $$$n$$$ 行,每行恰好包含 $$$n$$$ 字符,并且仅由零和一组成。这些行描述了矩阵元素中的值。

保证所有测试用例的 $$$n^2$$$ 值之和不超过 $$$4 \cdot 10^6$$$。

输出

对于每个测试用例,输出使 $$$A$$$ 矩阵统一所需的最少 burles 数。换句话说,打印对矩阵应用循环移位以使 $$$A$$$ 矩阵变为酉后所需的最小异或运算数。

示例

输入 #1

4
3
010
011
100
5
00010
00001
10000
01000
00100
2
10
10
4
1111
1011
1111
1111

输出 #1

1
0
2
11

注意

在第一个测试用例中,您可以执行以下操作:首先,将所有行循环下移,然后矩阵的主对角线将仅包含“1”。然后,有必要对不在主对角线上的唯一“1”应用异或运算。

在第二个测试用例中,您可以通过应用操作 $$$2$$$ 来创建酉矩阵 - 将行向上循环移位两次到矩阵。