Problem 0236 : Alien Messages

問題概要

日本語なので本文参照
（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0236&lang=jp）

解法

碁盤をグラフと見ると、求めるのはハミルトン閉路（NP完全）
グラフは制限がきついので、何か上手い方法があるのかと思ったけど、思い浮かばないので無理やりメモ化探索。

パスによりグラフが二つ以上に分断されてしまうと、もう閉路を作るのは無理になるので枝刈りできる。
盤のサイズが7x7で障害物なしの場合だけひと桁局面数が多いので、そこだけアドホックにNoを出す。
後はビット演算+ハッシュなどでちまちま高速化。

ソースコード

int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int w,h,sy,sx; ll goal=0;

bool v[7][7];
void nul(int y,int x){
	v[y][x]=1;
	rep(d,4){
		int ny=y+dy[d],nx=x+dx[d];
		if(ny<0||nx<0||ny>=h||nx>=w||v[ny][nx])continue;
		nul(ny,nx);
	}
}
bool separate(ll c){
	rep(i,h)rep(j,w)v[i][j]=c&1ll<<i*w+j;
	int cnt=0;
	rep(i,h)rep(j,w)if(!v[i][j]){
		if(cnt++>0)return 1;
		nul(i,j);
	}
	return 0;
}
const int sz=1000003;
ll hash[sz];
bool ins(ll v){
	ll h=v%sz;
	for(;hash[h]!=~0ll;h=(h+1)%sz)if(hash[h]==v)return 1;
	hash[h]=v;
	return 0;
}

bool rec(int y,int x, ll c){
	if(ins(c<<6|y<<3|x))return 0;
	
	rep(d,4){
		int ny=y+dy[d],nx=x+dx[d];
		if(ny<0||nx<0||ny>=h||nx>=w||(c&1ll<<ny*w+nx))continue;
		ll nc=c|1ll<<ny*w+nx;
		
		if(nc==goal&&ny==sy&&nx==sx)return 1;
		if(!separate(nc)&&rec(ny,nx,nc))return 1;
	}
	return 0;
}
int main(){
	while(cin>>w>>h,w){
		sy=-1; sx=-1;
		ll c=0; int t;
		rep(i,h)rep(j,w){
			cin>>t;
			if(t)c^=1ll<<i*w+j;
		}
		goal=(1ll<<h*w)-1;
		
		if(h>4&&w>4&&c==0){
			if(h%2&&w%2)cout<<"No"<<endl;
			else cout<<"Yes"<<endl;
			continue;
		}
		rep(i,h)rep(j,w)if(!(c&1ll<<i*w+j)){
			int cnt=0;
			rep(d,4){
				int ny=i+dy[d],nx=j+dx[d];
				if(ny<0||nx<0||ny>=h||nx>=w||(c&1ll<<ny*w+nx))cnt++;
			}
			if(cnt>2)goto OUT;
		}
		
		rep(i,h)rep(j,w-1)if((c&1ll<<i*w+j)+(c&1ll<<i*w+j+1)==0){
			sy=i; sx=j; goto OUT;
		}
		OUT:if(sy<0){
			cout<<"No"<<endl; continue;
		}
		rep(i,sz)hash[i]=~0ll;
		cout<<(rec(sy,sx,c)?"Yes":"No")<<endl;
	}
	return 0;
}