← 返回题目列表

Codeforces · 1703/E

E. 镜子网格

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

给你一个方形网格,其中包含 $$$n$$$ 行和 $$$n$$$ 列。每个单元格包含 $$$0$$$ 或 $$$1$$$。

在操作中,您可以选择网格的一个单元格并将其翻转(从 $$$0 \ 到 1$$$ 或 $$$1 \ 到 0$$$)。求获得旋转 $$$0^{\circ}$$$、$$$90^{\circ}$$$、$$$180^{\circ}$$$ 和 $$$270^{\circ}$$$ 时保持不变的正方形所需的最少运算次数。

下图显示了网格所有旋转的示例。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$) — 网格的大小。

接下来是 $$$n$$$ 行,每行包含 $$$n$$$ 个字符 $$$a_{i,j}$$$ ($$$0 \leq a_{i,j} \leq 1$$$) — 每个单元格中写入的数字。

输出

对于每个测试用例,输出一个整数 - 使正方形看起来相同旋转 $$$0^{\circ}$$$、$$$90^{\circ}$$$、$$$180^{\circ}$$$ 和 $$$270^{\circ}$$$ 所需的最少操作数。

示例

输入 #1

5
3
010
110
010
1
0
5
11100
11011
01011
10011
11000
5
01000
10101
01010
00010
01001
5
11001
00000
11111
10110
01111

输出 #1

1
0
9
7
6

注意

在第一个测试用例中,我们可以执行一个操作来使网格 $$$\begin{matrix}0 & 1 & 0\\ 1 & 1 & \color{red}{1}\\ 0 & 1 & 0\end{matrix}$$$。现在,正方形的所有旋转都是相同的。

在第二个测试用例中,正方形的所有旋转都已经相同,因此我们不需要任何翻转。