D - 让它们变为偶数

本题SPJ缺失

得分：400分

问题描述

有一个由$H$行$W$列组成的方块格子。第$i$行第$j$列的格子称为第$(i, j)$个格子。

在第$(i, j)$个格子中有$a_{ij}$个硬币。

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

操作：选择一个之前没有选择过的格子，并且其中有一个或多个硬币，然后将其中一个硬币移动到其上下左右相邻的一个格子中。

最大化包含偶数个硬币的格子数量。

约束

• 输入中的所有值都是整数。
• $1 \leq H, W \leq 500$
• $0 \leq a_{ij} \leq 9$

输入

从标准输入中按以下格式输入：

$H$ $W$

$a_{11}$ $a_{12}$ $...$ $a_{1W}$

$a_{21}$ $a_{22}$ $...$ $a_{2W}$

:

$a_{H1}$ $a_{H2}$ $...$ $a_{HW}$

输出

打印一系列操作，以以下格式最大化包含偶数个硬币的格子数量：

N
y_1 x_1 y_1' x_1'
y_2 x_2 y_2' x_2'
:
y_N x_N y_N' x_N'

即，第一行打印一个整数$N$，$N$在$0$和$H \times W$之间（包括$0$和$H \times W$），表示操作的数量。

在第$(i+1)$行（$1 \leq i \leq N$），打印四个整数$y_i, x_i, y_i'$和$x_i'$（$1 \leq y_i, y_i' \leq H$且$1 \leq x_i, x_i' \leq W$），表示第$i$个操作。这四个整数表示将放在第$(y_i, x_i)$个格子中的一个硬币移动到上下左右相邻的一个格子，即$(y_i', x_i')$。

请注意，如果指定的操作违反了问题陈述中的规定或者输出格式无效，将会导致"错误答案"。

2 3
1 2 3
0 1 1

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

在以下一系列操作之后，每个格子都包含偶数个硬币：

• 将第$(2, 2)$格子中的硬币移动到$(2, 3)$。
• 将第$(1, 1)$格子中的硬币移动到$(1, 2)$。
• 将第$(1, 3)$格子中的一个硬币移动到$(1, 2)$。

3 2
1 0
2 1
1 0

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

1 5
9 9 9 9 9

2
1 1 1 2
1 3 1 4