読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

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

yukicoder 作問

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

問題

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

解法

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

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

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

f:id:kmjp:20141205000621p:plain

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

  • HかWが1で、もう片方が3以上の場合。同じ場所を2回以上通らないと全セルをたどれない。
  • HもWも奇数の場合。このとき巡回路が存在しないことは以下のように証明できる。
    • グリッドを市松模様状に塗っておく。始点が白マスの場合、最初の移動は黒マス、2回目の移動は白マス…と交互にたどる。
    • f:id:kmjp:20141205000638p:plain
    • 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が3以上だと条件を満たさない
		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;
}

まとめ

問題文作るの難しいね。

広告を非表示にする