P12637 [UOI 2020] Golden Field

哥萨克人 Vus 偶然发现了一块 $n \times m$ 平方米的矩形田地。这块田地有 $n$ 行 $m$ 列，行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。 Vus 注意到某些方格中有金币：位于第 $i$ 行第 $j$ 列的方格中恰好有 $a_{ij}$ 枚金币。 如果只是简单地捡起所有金币，对 Vus 来说太容易了，因此他决定只从金币数量为偶数的方格中收取金币。 然而这个任务对他来说还是太简单，于是 Vus 决定通过以下方式移动金币：他可以将某个方格中的全部金币转移到任意相邻的方格中。两个方格相邻当且仅当它们共享一条边。他可以执行任意次数的这种转移操作。 现在 Vus 想知道他最多能收取多少金币。请你帮他计算这个最大值，并告诉他应该如何移动金币才能达到这个目标。 注意 Vus 不需要最小化转移操作的次数，他只需要最大化最终收取的金币数量。

第一行包含两个整数 $t$ 和 $g$（$1 \leq t \leq 10$，$0 \leq g \leq 6$）——测试用例数量和测试组编号。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 50$）——田地的尺寸。 接下来的 $n$ 行每行包含 $m$ 个整数 $a_{i1}, a_{i2}, \dots, a_{im}$（$0 \leq a_{ij} \leq 100$）——每个方格中的金币数量。 不保证田地中至少有一枚金币。

对于每个测试用例，按以下格式输出： 第一行输出一个整数——Vus 能收取的最大金币数量。 第二行输出一个整数 $p$（$0 \leq p \leq 10\,000$）——需要执行的转移操作次数。注意不需要最小化 $p$ 的值。 接下来的 $p$ 行，每行输出四个整数 $x_1$, $y_1$, $x_2$, $y_2$（$1 \leq x_1, x_2 \leq n$，$1 \leq y_1, y_2 \leq m$），表示将位于 $(x_1, y_1)$ 的方格中的所有金币转移到 $(x_2, y_2)$ 的方格中。 如果有多个正确答案，输出任意一个即可。题目保证存在最优解，且转移操作次数不超过 $10\,000$。

在第一个样例中，Vus 可以先将 $(1, 2)$ 方格中的所有金币转移到 $(2, 2)$，此时田地状态为： $$\begin{array}{cc} 4 & 0 & 1\\ 9 & 7 & 0\\ \end{array}$$ 然后将 $(2, 2)$ 方格中的金币转移到 $(2, 1)$，田地状态变为： $$\begin{array}{cc} 4 & 0 & 1\\ 16 & 0 & 0\\ \end{array}$$ 因此最终收取的金币数量为 $4+16=20$。 在第二个样例中，Vus 可以先将 $(1, 1)$ 方格中的金币转移到 $(1, 2)$，此时田地状态为： $$\begin{array}{c} 0 & 5 & 5 & 4 \end{array}$$ 然后将 $(1, 2)$ 方格中的金币转移到 $(1, 3)$，田地状态变为： $$\begin{array}{c} 0 & 0 & 10 & 4 \end{array}$$ 因此最终收取的金币数量为 $10+4=14$。 ### 评分标准 - （$14$ 分）$n=1$，所有 $a_{ij}$ 为偶数； - （$16$ 分）$n=1$，所有 $a_{ij}$ 为奇数； - （$19$ 分）$n=1$； - （$14$ 分）$n,m>1$，所有 $a_{ij}$ 为偶数； - （$17$ 分）$n,m>1$，所有 $a_{ij}$ 为奇数； - （$20$ 分）$n,m>1$。 翻译由 DeepSeek V3 完成