D - Make Them Even

Contest Duration: 2018-09-08(Sat) 12:00 - 2018-09-08(Sat) 13:40 (local time) (100 minutes) Back to Home

D - Make Them Even Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $400$ 点

問題文

縦 $H$ 行横 $W$ 列に区切られたマス目があり、上から $i$ 番目、左から $j$ 列目のマスをマス $(i, j)$ と呼びます。

マス $(i, j)$ には $a_{ij}$ 枚のコインが置かれています。

あなたは以下の操作を何度でも行うことができます。

操作: まだ選んだことのないマスのうち $1$ 枚以上のコインが置かれているマスを $1$ つ選び、そのマスに置かれているコインのうち $1$ 枚を上下左右に隣接するいずれかのマスに移動する

偶数枚のコインが置かれたマスの数を最大化してください。

制約

入力はすべて整数である
$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'$

すなわち、 $1$ 行目には操作の回数を表す $0$ 以上 $H \times W$ 以下の整数 $N$ を出力せよ。

$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 となるので注意せよ。

入力例 1Copy

Copy

2 3
1 2 3
0 1 1

出力例 1Copy

Copy

次のように操作を行えば、全てのマスに置かれたコインの数を偶数にできます。

マス $(2, 2)$ に置かれているコインのうち $1$ 枚をマス $(2, 3)$ に移動します
マス $(1, 1)$ に置かれているコインのうち $1$ 枚をマス $(1, 2)$ に移動します
マス $(1, 3)$ に置かれているコインのうち $1$ 枚をマス $(1, 2)$ に移動します

入力例 2Copy

Copy

出力例 2Copy

Copy

入力例 3Copy

Copy

1 5
9 9 9 9 9

出力例 3Copy

Copy

2
1 1 1 2
1 3 1 4

Score : $400$ points

Problem Statement

There is a grid of square cells with $H$ horizontal rows and $W$ vertical columns. The cell at the $i$ -th row and the $j$ -th column will be denoted as Cell $(i, j)$ .

In Cell $(i, j)$ , $a_{ij}$ coins are placed.

You can perform the following operation any number of times:

Operation: Choose a cell that was not chosen before and contains one or more coins, then move one of those coins to a vertically or horizontally adjacent cell.

Maximize the number of cells containing an even number of coins.

Constraints

All values in input are integers.
$1 \leq H, W \leq 500$
$0 \leq a_{ij} \leq 9$

Input

Input is given from Standard Input in the following format:

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

Output

Print a sequence of operations that maximizes the number of cells containing an even number of coins, in the following format:

 $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'$

That is, in the first line, print an integer $N$ between $0$ and $H \times W$ (inclusive), representing the number of operations.

In the $(i+1)$ -th line ( $1 \leq i \leq N$ ), print four integers $y_i, x_i, y_i'$ and $x_i'$ ( $1 \leq y_i, y_i' \leq H$ and $1 \leq x_i, x_i' \leq W$ ), representing the $i$ -th operation. These four integers represents the operation of moving one of the coins placed in Cell $(y_i, x_i)$ to a vertically or horizontally adjacent cell, $(y_i', x_i')$ .

Note that if the specified operation violates the specification in the problem statement or the output format is invalid, it will result in Wrong Answer.

Sample Input 1Copy

Copy

2 3
1 2 3
0 1 1

Sample Output 1Copy

Copy

Every cell contains an even number of coins after the following sequence of operations:

Move the coin in Cell $(2, 2)$ to Cell $(2, 3)$ .
Move the coin in Cell $(1, 1)$ to Cell $(1, 2)$ .
Move one of the coins in Cell $(1, 3)$ to Cell $(1, 2)$ .

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

1 5
9 9 9 9 9

Sample Output 3Copy

Copy

2
1 1 1 2
1 3 1 4