Codeforces #292 Div1 B. Drazil and Tiles

ありがちなドミノタイル問題を少し改変したもの。
http://codeforces.com/contest/516/problem/B

問題

N*Mの２次元グリッドが与えられる。
一部のセルは埋まっている。

空きセルを、1*2のサイズのタイルを敷き詰めて埋めたい。
全ての空きセルを埋めることができ、かつ埋め方が一意であればそれを答えよ。

解法

埋め方が一意に決まる場所、すなわち隣接セルが１か所しかない場所から埋めていけば良い。
これで全部埋まれば全体の埋め方が一意に決まる。

int H,W;
string S[2020];
int emp[2020][2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	queue<int> Q;
	FOR(y,H) FOR(x,W) if(S[y][x]=='.') {
		emp[y][x] += (y>0&&S[y-1][x]=='.');
		emp[y][x] += (y<H-1&&S[y+1][x]=='.');
		emp[y][x] += (x>0&&S[y][x-1]=='.');
		emp[y][x] += (x<W-1&&S[y][x+1]=='.');
		if(emp[y][x]==1) Q.push(y*10000+x);
	}
	
	while(Q.size()) {
		int k=Q.front();
		Q.pop();
		y=k/10000,x=k%10000;
		if(S[y][x]!='.') continue;
		
		int my=-1,mx=-1;
		if(y>0 && S[y-1][x]=='.') {
			S[y-1][x]='^';
			S[y][x]='v';
			my=y-1;
			mx=x;
		}
		if(y<H-1 && S[y+1][x]=='.') {
			S[y+1][x]='v';
			S[y][x]='^';
			my=y+1;
			mx=x;
		}
		if(x>0 && S[y][x-1]=='.') {
			S[y][x-1]='<';
			S[y][x]='>';
			my=y;
			mx=x-1;
		}
		if(x<W-1 && S[y][x+1]=='.') {
			S[y][x+1]='>';
			S[y][x]='<';
			my=y;
			mx=x+1;
		}
		if(my>-1) {
			FOR(i,4) {
				int dd[4]={1,0,-1,0};
				int ty=y+dd[i],tx=x+dd[i^1];
				if(ty<0 || ty>=H || tx<0 || tx>=W) continue;
				if(S[ty][tx]!='.') continue;
				emp[ty][tx]--;
				if(emp[ty][tx]==1) Q.push(ty*10000+tx);
			}
			FOR(i,4) {
				int dd[4]={1,0,-1,0};
				int ty=my+dd[i],tx=mx+dd[i^1];
				if(ty<0 || ty>=H || tx<0 || tx>=W) continue;
				if(S[ty][tx]!='.') continue;
				emp[ty][tx]--;
				if(emp[ty][tx]==1) Q.push(ty*10000+tx);
			}
		}
	}
	
	FOR(y,H) FOR(x,W) if(S[y][x]=='.') return _P("Not unique\n");
	FOR(y,H) cout<<S[y]<<endl;
}

解法

埋められるかどうかを求めるだけで良いと思うのだけど、埋め方を答えるの無駄にコードが長くなってしまった。