yukicoder : No.86 TVザッピング(2)

最初★３にしたけど、難易度設定調整後だと★４かな。
http://yukicoder.me/problems/195

問題

H*Wのグリッドがあり、各セルの移動可否が与えられる。
任意のセルから開始し、隣接セルを辿って移動可能なセルをすべて１回ずつたどり、最後に開始セルに戻ることができるか答えよ。

なお、隣接セル間を移動する際、前と同じ向きか、90度左向きのセルにしか移動できない。

解法

この問題は、左折は何回でも可能、右折は最大１回まで可能な巡回路の有無を答える問題となる。
問題文からは右折はできないように見えるが、右折したいセルを始点にすれば、そこだけは右折できる（サンプル３がその例）。

右折が０回または１回で構成できる図形は以下のいずれかである。（白マスを移動可能なセル、黒マスを移動不可能なセルとする）

• 右折が０回の場合、サンプル1のように高さ・幅ともに２以上の長方形(始点はどこでも良い)
• 
• 右折が１回の場合、サンプル3のように長方形のうち１か所角が凹んだ六角形(始点は★のみ可)
• 
  • 凹む箇所は他の角でも良い。
  • 

それ以外の形状が存在しないことを示す。
左折回数をL、右折回数をRとする。
(L+R)頂点の多角形の内角を考えるとなので変形すると。
Rが0か1なので、Lは4か5、よって条件を満たすのは四角形と六角形だけである。

あとは、移動可能なセルが上記長方形または六角形になるか判定すればよい。
以下のコードでは、長方形または六角形を成す頂点の候補を求め、それらの頂点を結ぶセルがすべて移動可能セルで、かつそれらのセルの数が、全移動可能セルと一致するか判定しているかチェックしている。

長方形・六角形の候補の作り方だが、長方形については、移動可能セルのうち最も左・右・上・下のセルを囲う長方形を考えればよい。
六角形については、上記長方形の内部のセルを始点候補として総当たりし、４か所の角が落ちるケースをそれぞれ探索すればよい。

「頂点を結ぶセルがすべて移動可能セルか」の判定は、事前に移動可能なセルの横方向・縦方向の累積和を取っておくと高速に行える。

なお、他の解答は始点を総当たりして探索してる人が多かったようです。それは想定外でした…。

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

int N,M;
string S[101];

int total;
int sumH[101][101];
int sumV[101][101];

int get_sumH(int y, int l, int r) {
	// 横方向、S[y][l]～S[y][r]がすべて有効か？有効でないなら適当な負の値を返す。
	if (sumH[y][r+1] - sumH[y][l] == r+1-l) return r+1-l;
	else return -100000;
}

int get_sumV(int x, int t, int b) {
	// 縦方向、S[t][x]～S[b][x]がすべて有効か？有効でないなら適当な負の値を返す。
	if (sumV[b+1][x] - sumV[t][x] == b+1-t) return b+1-t;
	else return -100000;
}

int main(int argc,char** argv){
	int x,y;
	
	// 入力
	cin >> N >> M;
	for(y=0; y<N; y++) cin >> S[y];
	
	// 有効なチャンネル数を数え上げしつつ、
	// 左端・右端・上端・下端の位置を求める
	int left=M-1, right=0, top=N-1, bottom=0;
	for(y=0; y<N; y++) {
		for(x=0; x<M; x++) {
			if (S[y][x] == '.') {
				total++;
				left = min(left,x);
				right = max(right,x);
				top = min(top,y);
				bottom = max(bottom,y);
			}
		}
	}
	
	// 高さと幅は2以上でなければならない
	if (right - left < 1 || bottom - top < 1) {
		cout << "NO" << endl;
		return 0;
	}
	
	// 累積和を作っておく
	for(y=0; y<N; y++) for(x=0; x<M; x++) sumH[y][x+1] = sumH[y][x] + (S[y][x]=='.');
	for(y=0; y<N; y++) for(x=0; x<M; x++) sumV[y+1][x] = sumV[y][x] + (S[y][x]=='.');
	
	int ok = 0;
	
	// 長方形ルートかどうかチェック
	int sum=0;
	sum += get_sumH(top,left,right) + get_sumH(bottom,left,right); // 上下の辺の有効チャンネル数
	sum += get_sumV(left,top,bottom) + get_sumV(right,top,bottom); // 左右の辺の有効チャンネル数
	sum -= 4; // 4つ角を二重カウントしているので、その分減らす
	if (sum == total) ok = 1;
	
	// 1回右折する点が内部にあるかチェック
	for(y=top+1; y<=bottom-1; y++) {
		for(x=left+1; x<=right-1; x++) {
			if (S[y][x] == '.') {
				
				// 右上が欠けるケース
				sum = get_sumH(top,left,x) + get_sumH(y,x,right) + get_sumH(bottom,left,right);
				sum += get_sumV(left,top,bottom) + get_sumV(x,top,y) + get_sumV(right,y,bottom);
				sum -= 6;
				if (sum == total) ok=1;
				
				// 右下が欠けるケース
				sum = get_sumH(top,left,right) + get_sumH(y,x,right) + get_sumH(bottom,left,x);
				sum += get_sumV(left,top,bottom) + get_sumV(x,y,bottom) + get_sumV(right,top,y);
				sum -= 6;
				if (sum == total) ok=1;
				
				// 左上が欠けるケース
				sum = get_sumH(y,left,x) + get_sumH(top,x,right) + get_sumH(bottom,left,right);
				sum += get_sumV(left,y,bottom) + get_sumV(x,top,y) + get_sumV(right,top,bottom);
				sum -= 6;
				if (sum == total) ok=1;
				
				// 左下が欠けるケース
				sum = get_sumH(top,left,right) + get_sumH(y,left,x) + get_sumH(bottom,x,right);
				sum += get_sumV(left,top,y) + get_sumV(x,y,bottom) + get_sumV(right,top,bottom);
				sum -= 6;
				if (sum == total) ok=1;
			}
		}
	}
	
	if (ok==1) cout << "YES" << endl;
	else cout << "NO" << endl;
	
	return 0;
}

まとめ

他の回答者の探索解の方がわかりやすいかも…。