AtCoder题解｜ABC 109D Make Them Even

题目信息 📚

【题目描述】

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.

【输入】

The input is given from Standard Input in the following format:

$H$ $W$

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

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

$\vdots$

$a_{H1}$ $a_{H2}$ … $a_{HW}$

【输出】

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$

$\vdots$

$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 represent 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.

【数据范围】

All values in input are integers.

$1 \leq H, W \leq 500$
$0 \leq a_{ij} \leq 9$

【输入样例1】

2 3
1 2 3
0 1 1

【输出样例1】

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)$.

【输入样例2】

【输出样例2】

【输入样例3】

1 5
9 9 9 9 9

【输出样例3】

2
1 1 1 2
1 3 1 4

【题目来源】

https://atcoder.jp/contests/abc109/tasks/abc109_d

题目解析 🍉

【题目分析】

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 600;
int a[N][N], h, w, cnt;
bool used[N][N];
typedef struct Line {
    int x, y, xn, yn;
} Line;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> h >> w;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> a[i][j];
        }
    }

    vector<Line> ans;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j < w; j++) {
            if (a[i][j] % 2 == 1) {
                used[i][j] = true;
                a[i][j]--;
                a[i][j + 1]++;
                cnt++;

                Line tmp = {i, j, i, j + 1};
                ans.push_back(tmp);
            }
        }
    }

    for (int i = 1; i < h; i++) {
        if (a[i][w] % 2 == 1) {
            used[i][w] = true;
            a[i][w]--;
            a[i + 1][w]++;
            cnt++;
            Line tmp = {i, w, i + 1, w};
            ans.push_back(tmp);
        }
    }
    cout << cnt << endl;
    for (auto t: ans) {
        cout << t.x << " " << t.y << " " << t.xn << " " << t.yn << endl;
    }

    return 0;
}