分数: 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 之间 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第次操作。这四个整数代表移动放置在Cell中的一枚硬币的操作 (y_i, x_i) 到垂直或水平相邻的单元格, (y_i', x_i').
注意,如果指定的操作违反了问题陈述中的规范或者输出格式无效,将会导致 错误答案.
示例输入 1
2 3 1 2 3 0 1 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).
示例输入 2
3 2 1 0 2 1 1 0
示例输出 2
3 1 1 1 2 1 2 2 2 3 1 3 2
示例输入 3
1 5 9 9 9 9 9
示例输出 3
2 1 1 1 2 1 3 1 4