Codeforces #209 Div2. E. Neatness

若干実装が面倒な問題だが、なかなか面白い。
なんとかノーヒントで解けた。
http://codeforces.com/contest/359/problem/E

問題

部屋がグリッド状に配置されており、各部屋の電気のon/offの状態およびプレイヤーの初期値が与えられる。
プレイヤーは以下の行動をとることができる。

• 今いる部屋の電気を消す
• 今いる部屋の電気を点ける
• 上下左右いずれかの隣接する部屋について、その部屋もしくはその方向の奥の部屋に電気がついている部屋があれば、隣接する部屋に移動する。

上記の処理を繰り返す場合、全ての電気を消せるか答えよ。
また、消せるなら行動順を示せ。

解法

以下の手順で処理できる。

• 初期位置からDFSですべての電気の付いた部屋をたどるパスを構築する。パスは木構造になる。
  • 移動可能な部屋から、まだパスにつながっていない電気の付いた部屋が見えるならそこをつなぐ
  • パスにつなげない電気の付いた部屋が残る場合、全ての電気を消せない。
• パスをDFSでたどり、初期位置に戻る。その時、電気がついてない部屋があればつけながら移動する。
• 再度パスをDFSでたどり、行き止まりに到達して戻る際に電気を消しながら戻る。

一旦パスの電気を全部つけて、初期位置から遠いところから戻りながら消していくのがコツ。
この問題は行動ターン数が300万回となっており、これはマスの数の12倍である。
実際は、各マスは2回行って戻るのと、電気をつけて消すので最大6回までしか構造しないので、行動ターン数は150万回以下で終わる。

int N,X,Y;
int mat[501][501];
int vis[501][501];
int LM[501],RM[501],TM[501],BM[501];
char str[3000002];
char* P;

void dfs(int cy,int cx,int pre,bool on) {
	char move[16]="*LR*U***D";
	int i;
	if(on && (mat[cy][cx]&1)==0) *P++ = '1';
	
	if((vis[cy][cx]&1) && (pre!=1)) *P++ = 'L', dfs(cy,cx-1,2,on);
	if((vis[cy][cx]&2) && (pre!=2)) *P++ = 'R', dfs(cy,cx+1,1,on);
	if((vis[cy][cx]&4) && (pre!=4)) *P++ = 'U', dfs(cy-1,cx,8,on);
	if((vis[cy][cx]&8) && (pre!=8)) *P++ = 'D', dfs(cy+1,cx,4,on);
	if(!on) *P++ = '2';
	if(pre!=0) *P++ = move[pre];
}


void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>Y>>X;
	X--; Y--;
	FOR(y,N) FOR(x,N) cin>>mat[y][x];
	FOR(y,N) LM[y]=TM[y]=N, RM[y]=BM[y]=-1;
	l=0;
	mat[Y][X]|=2;
	FOR(y,N) FOR(x,N) if(mat[y][x]) {
		l++;
		if(LM[y]>x) LM[y]=x;
		RM[y]=x;
		if(TM[x]>y) TM[x]=y;
		BM[x]=y;
	}
	
	if(l==1 && (mat[Y][X]&1)) return _P("YES\n2\n");
	P=str;
	stack<int> Q;
	Q.push(Y*1000+X);
	while(!Q.empty()) {
		int k=Q.top();
		Q.pop();
		int cx=k%1000,cy=k/1000;
		
		TM[cx]=min(TM[cx],cy);
		BM[cx]=max(BM[cx],cy);
		LM[cy]=min(LM[cy],cx);
		RM[cy]=max(RM[cy],cx);
		
		FOR(i,4) {
			int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
			int tx=cx+dx[i],ty=cy+dy[i];
			if(tx<0 || ty<0 || tx>=N || ty>=N) continue;
			if(dy[i]>0 && BM[cx]<ty) continue;
			if(dy[i]<0 && TM[cx]>ty) continue;
			if(dx[i]>0 && RM[cy]<tx) continue;
			if(dx[i]<0 && LM[cy]>tx) continue;
			if(mat[ty][tx] & 2) continue;
			mat[ty][tx]|=2;
			if(dx[i]<0) vis[cy][cx] |= 1,vis[ty][tx] |= 2;
			if(dx[i]>0) vis[cy][cx] |= 2,vis[ty][tx] |= 1;
			if(dy[i]<0) vis[cy][cx] |= 4,vis[ty][tx] |= 8;
			if(dy[i]>0) vis[cy][cx] |= 8,vis[ty][tx] |= 4;
			Q.push(ty*1000+tx);
		}
	}
	
	FOR(y,N) FOR(x,N) if(mat[y][x]==1) return _P("NO\n");
	dfs(Y,X,0,true);
	dfs(Y,X,0,false);
	_P("YES\n%s\n",str);
}

まとめ

解法はすんなり思いついたけど実装に手こずった。
CF209はどれもWA繰り返し過ぎてるな…。