yukicoder : No.85 TVザッピング(1)

初の作問。
http://yukicoder.me/problems/156

問題

縦H段、横W列の長方形のグリッドがある。
始点のセルの位置が与えられるので、隣接セルを順々にたどり、全てのセルを１個ずつ経由して始点に戻る巡回路は存在するか答えよ。

解法

巡回路が存在する場合、どこを始点としても巡回することができる。
よって始点の位置は無視してよい。

巡回できるケースは以下の２通りである。

• サイズが1*2または2*1の場合。
• H, Wがいずれも２以上で、どちらかが偶数の場合。
  • 例えばHが偶数の場合、以下のようにたどればよい。Wが偶数の場合も90度回転して同様に考えられる。

巡回できないケースは、上記の逆である。

• HかWが1で、もう片方が3以上の場合。同じ場所を２回以上通らないと全セルをたどれない。
• HもWも奇数の場合。このとき巡回路が存在しないことは以下のように証明できる。
  • グリッドを市松模様状に塗っておく。始点が白マスの場合、最初の移動は黒マス、２回目の移動は白マス…と交互にたどる。
  • 
  • HもWも奇数なので総移動回数H*Wは奇数である。
  • 最後は始点である白マスに戻ってこなければならないが、白マスを通るのは偶数回目の移動である。つまり最後に白マスに戻ってくることはできない。

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

int main(int argc,char** argv){
	int H, W, C;
	
	cin >> H >> W >> C;
	
	// Hが小さくなるようにswap
	if(H > W) swap(H,W);
	
	if(H==1) {
		// H==1の時、Wが３以上だと条件を満たさない
		if(W==2) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
	}
	else {
		// H,W>1なら、縦横どちらかが偶数なら条件を満たす。
		if (H*W % 2 == 0) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
	}
	
	return 0;
}

まとめ

問題文作るの難しいね。