← 返回题目列表

AtCoder · abc109_d

D. 让他们扯平

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

分数: 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