← 返回题目列表

Codeforces · 1366/C

C. 回文路径

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

给您一个矩阵,其中包含 $$$n$$$ 行(编号从 $$$1$$$ 到 $$$n$$$)和 $$$m$$$ 列(编号从 $$$1$$$ 到 $$$m$$$)。第$$$i$$$行第$$$j$$$列的单元格中写入数字$$$a_{i, j}$$$,每个数字要么是$$$0$$$,要么是$$$1$$$。

筹码最初位于单元格 $$$(1, 1)$$$ 中,它将被移动到单元格 $$$(n, m)$$$ 中。在每次移动期间,它要么移动到当前行中的下一个单元格,要么移动到当前列中的下一个单元格(如果当前单元格是 $$$(x, y)$$$,则移动后它可以是 $$$(x + 1, y)$$$ 或 $$$(x, y + 1)$$$)。芯片不能离开矩阵。

考虑芯片从 $$$(1, 1)$$$ 到 $$$(n, m)$$$ 的每条路径。如果第一个单元格中的数字等于最后一个单元格中的数字,第二个单元格中的数字等于倒数第二个单元格中的数字,依此类推,则路径称为回文路径。

您的目标是更改最小数量的单元格中的值,以便每条路径都是回文的。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n, m \le 30$$$) — 矩阵的维度。

接下来是 $$$n$$$ 行,第 $$$i$$$ 行包含 $$$m$$$ 整数 $$$a_{i, 1}$$$, $$$a_{i, 2}$$$, ..., $$$a_{i, m}$$$ ($$$0 \le a_{i, j} \le 1$$$)。

输出

对于每个测试用例,打印一个整数 - 必须更改的最小单元数,以便矩阵中的每条路径都是回文。

示例

输入 #1

4
2 2
1 1
0 1
2 3
1 1 0
1 0 0
3 7
1 0 1 1 1 1 1
0 0 0 0 0 0 0
1 1 1 1 1 0 1
3 5
1 0 1 0 0
1 1 1 1 0
0 0 1 0 0

输出 #1

0
3
4
4

注意

前三个测试用例中的结果矩阵:

$$$\begin{pmatrix} 1 & 1\\ 0 & 1 \end{pmatrix}$$$

$$$\begin{pmatrix} 0 & 0 & 0\\ 0 & 0 & 0 \end{pmatrix}$$$

$$$\begin{pmatrix} 1 & 0 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 & 1 & 0 & 1 \end{pmatrix}$$$