Yukicoder085 TVザッピング(1)

問題概要

yuki君が持っているテレビのリモコンには、ボタンが縦$N$段、横$M$列の長方形状に計$N×M$個並んでいる。
リモコンの$X$段目$Y$列目のボタンを押すと、テレビでチャンネル$((X−1)×M+Y)$を見ることができる。
（サンプルケース1の解説に具体例が記載されている）

yuki君はさっきチャンネル$C$のボタンを押し、そのままチャンネル$C$を見ている。
ところがyuki君は途中で他のチャンネルの内容を一通り見てみたくなった。
yuki君は素早く全チャンネルを巡回して元のチャンネル$C$に戻るため、以下のルールで順にボタンを押す。
最初に押すボタンは、さっき押したチャンネル$C$のボタンと上下左右いずれかに隣接したボタンである。
以降、直前に押したボタンと上下左右いずれかに隣接したボタンを押していく。
チャンネル$C$以外の全てのチャンネルのボタンをちょうど1回ずつ押した上で、最後にまたチャンネル$C$のボタンを押す。
$N, M, C$が与えられたとき、上記ルールをすべて満たすボタンの押し順が存在するか答えよ。

$N,M\leqq10^2$、$C\leqq N*M$

yukicoder085

解法

odd*oddが到達できないことは二部グラフとであることとパリティで証明できる。
移動回数は奇数回で、二部グラフ上を移動するが移動中のどこかで同じ色2回繰り返して移動しなければならない。
また1×Aのような長方形は無理だけど、1×1、1×2は例外的に戻れる。

計算量:$O(1)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        int H, W, C; cin >> H >> W >> C;
        if (H > W)swap(H, W);
        if ((H == 1 && W > 2) || ((H*W) % 2 == 1)) {
            cout << "NO" << endl;
        }
        else {
            cout << "YES" << endl;
        }
        return 0;
    }