AT_abc109_d [ABC109D] Make Them Even

题目描述

有一个被分成 $H$ 行 $W$ 列的网格，从上往下第 $i$ 行，从左往右第 $j$ 列的格子称为格子 $(i, j)$。

在格子 $(i, j)$ 上放有 $a_{ij}$ 枚硬币。

你可以进行如下操作任意次：

操作：从尚未被选中过且至少有 $1$ 枚硬币的格子中选择一个，将其中 $1$ 枚硬币移动到其上下左右相邻的某一个格子中。

请最大化网格中放有偶数枚硬币的格子的数量。

输入格式

输入以如下格式从标准输入读入。

$H$ $W$
$a_{11}$ $a_{12}$ ... $a_{1W}$
$a_{21}$ $a_{22}$ ... $a_{2W}$
$\vdots$
$a_{H1}$ $a_{H2}$ ... $a_{HW}$

输出格式

请输出一组操作序列，使得放有偶数枚硬币的格子的数量最大，格式如下：

$N$
$y_1$ $x_1$ $y_1'$ $x_1'$
$y_2$ $x_2$ $y_2'$ $x_2'$
$\vdots$
$y_N$ $x_N$ $y_N'$ $x_N'$

其中，第一行为操作次数 $N$，满足 $0 \leq N \leq H \times W$。

第 $i+1$ 行（$1 \leq i \leq N$）为第 $i$ 次操作，$y_i, x_i, y_i', x_i'$（$1 \leq y_i, y_i' \leq H$ 且 $1 \leq x_i, x_i' \leq W$），表示将格子 $(y_i, x_i)$ 中的 $1$ 枚硬币移动到其相邻的格子 $(y_i', x_i')$。

如果输出了题目未允许的操作，或输出格式不正确，将被判为 Wrong Answer。

样例 1

输入

2 3
1 2 3
0 1 1

输出

3
2 2 2 3
1 1 1 2
1 3 1 2

样例 2

输入

3 2
1 0
2 1
1 0

输出

3
1 1 1 2
1 2 2 2
3 1 3 2

样例 3

输入

1 5
9 9 9 9 9

输出

2
1 1 1 2
1 3 1 4

说明/提示

限制

• 所有输入均为整数。
• $1 \leq H, W \leq 500$
• $0 \leq a_{ij} \leq 9$

样例解释 1

按如下方式操作，可以使所有格子的硬币数都变为偶数：

• 将格子 $(2, 2)$ 的 $1$ 枚硬币移动到格子 $(2, 3)$
• 将格子 $(1, 1)$ 的 $1$ 枚硬币移动到格子 $(1, 2)$
• 将格子 $(1, 3)$ 的 $1$ 枚硬币移动到格子 $(1, 2)$

由 ChatGPT 4.1 翻译