けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

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

問題概要

 N \times M のマス目に整数値 (マス  (i, j) には  A_{i, j}) が書かれている。

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

制約

  •  1 \le N, M \le 100

考えたこと

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

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

というふうにすれば OK。

f:id:drken1215:20201114065426p:plain

コード

#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;
        }
    }
}