Maximum-Cup 2013 : I - 実績 : ヘビマスター

これも問題文を読み間違えて苦労した問題。
http://maximum-cup-2013.contest.atcoder.jp/tasks/maximum_2013_i

問題

二次元グリッドにおいて移動不可マスとヘビの初期状態が与えられる。
ヘビはヘビゲームの要領で移動できる。
ヘビの先頭が一筆書きの要領で、移動可能な全マスをたどることができるかを答えよ。

解法

グリッドサイズが小さいので、移動済みのマスをbitmapで保持し、塗りつぶしていけばよい。
初期状態でヘビの胴体があるマスは、先頭マスが数マス移動すると胴体が動いて先頭が移動可能となる点に留意。

int L,H,W;
string M[10];

int can(int cx,int cy,ll mask,int dir,int step) {
	
	if(mask == (1LL<<((H-2)*(W-2)))-1) return 1;
	int i,j,r;
	int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
	
	FOR(i,4) {
		int ty=cy+dy[i],tx=cx+dx[i],ng=0;
		if(tx<=0 || ty<=0 || tx>=W-1 || ty>=H-1 || i==(dir^1)) continue;
		if(mask&(1LL<<((ty-1)*(W-2)+(tx-1)))) ng=1;
		if(M[ty][tx]>='2' && M[ty][tx]<='9' && (L-(M[ty][tx]-'0'))>step) ng=1;
		if(ng) continue;
		if(can(tx,ty,mask | (1LL<<((ty-1)*(W-2)+(tx-1))),i,step+1)) return 1;
	}
	return 0;
}


void solve() {
	int f,i,j,k,l,x,y,sx,sy,px,py;
	
	while(1) {
		cin>>L>>H>>W;
		if(L==0) return;
		ll lm=0;
		string path("*",L);
		FOR(y,H) {
			cin>>M[y];
			for(x=1;x<W-1;x++) {
				if(y!=0 && y!=H-1) {
					if((M[y][x]=='#' || M[y][x]=='1')) lm |= 1LL<<((y-1)*(W-2)+(x-1));
					if(M[y][x]=='1') sx=x,sy=y;
					if(M[y][x]=='2') px=x,py=y;
				}
			}
		}
		int pdir=0;
		if(sx<px) pdir=0;
		if(sx>px) pdir=1;
		if(sy<py) pdir=2;
		if(sy>py) pdir=3;
		
		if(can(sx,sy,lm,pdir,0)) _P("Yes\n");
		else _P("No\n");
	}
}

まとめ

最初、同じマスを複数回移動可能と勘違いして、「こんなんTLEするじゃん…」とびっくりしてしまった。