AtCoder ABC #232 (M-SOLUTIONS プロコンオープン2021) : H - King's Tour

場合分けがごちゃごちゃになりすぎて間に合わず…。
https://atcoder.jp/contests/abc232/tasks/abc232_h

問題

H*Wのグリッド上で、(1,1)に置いたチェスのキングの駒を動かすことを考える。
全マス1回ずつ経由しつつ、最後(A,B)で止まるようなパスを1つ求めよ。

解法

こういう問題では、再帰的により小さく単純な問題に持ち込むのがセオリー。

• H=2またはW=2の場合は自明。
  • 例えばH=2の場合、(1,1)(2,1)(1,2)(2,2)....(1,B-1)(2,B-1)とジグザグに移動した後、(3-A,B)(3-A,B+1)...(3-A,W)と右に移動して(A,W)(A,W-1)...(A,B)と戻ればよい。
• H＞2かつW＞2の場合を考える。
  • もしB=1または(A,B)=(H-1,2)の場合、縦横逆にすする。
  • そうでない場合、(1,1)(2,1)....(H,1)(H,2)と移動すると、Wが1小さい問題に帰着できる。

int H,W,A,B;

vector<pair<int,int>> go(int H,int W,int A,int B) {
	vector<pair<int,int>> R;
	int y,x;
	if(H==2) {
		FOR(x,B) {
			R.push_back({0,x});
			R.push_back({1,x});
		}
		for(x=B;x<W;x++) R.push_back({A^1,x});
		for(x=W-1;x>=B;x--) R.push_back({A,x});
		
	}
	else if(W==2) {
		R=go(W,H,B,A);
		FORR2(y,x,R) swap(y,x);
	}
	else {
		if(B==0||(A==H-1&&B==1)) {
			R=go(W,H,B,A);
			FORR2(y,x,R) swap(y,x);
		}
		else {
			FOR(y,H) R.push_back({y,0});
			auto R2=go(H,W-1,H-1-A,B-1);
			FORR2(y,x,R2) R.push_back({H-1-y,x+1});
		}
	}
	
	
	return R;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>A>>B;
	A--,B--;
	auto R=go(H,W,A,B);
	FORR2(y,x,R) cout<<y+1<<" "<<x+1<<endl;
}

まとめ

これは分岐も少なくて賢いな…。