Codeforces Round #682 (Div. 2) C. Engineer Artem (R2000)

グリッドグラフは二部グラフ！！！

• 問題へのリンク

問題概要

のマス目に整数値 (マス には ) が書かれている。

各マスについて、「元の整数値のままにする」または「元の整数値に 1 を足したもの」をすることによって、どの隣接する 2 マスの値も互いに相異なる状態にせよ。

制約

• 

考えたこと

グリッドグラフは二部グラフという小ネタ問題としてすごい面白い！！ マス目を図のように市松模様に塗る。

• 黒いマスは偶数になるようにする
• 白いマスは奇数になるようにする

というふうにすれば OK。

コード

#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;

int main() {
    cin.tie(0); 
    ios::sync_with_stdio(false);

    int T;
    cin >> T;
    while (T--) {
        int N, M;
        cin >> N >> M;
        vector<vector<int>> a(N, vector<int>(M));
        for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) cin >> a[i][j];
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                if (a[i][j] % 2 != (i+j)%2) a[i][j] += 1;

                if (j) cout << " ";
                cout << a[i][j];
            }
            cout << endl;
        }
    }
}