TopCoder SRM 588 Div2 Hard GameInDarknessDiv2

Div1 Hardはまさかの1100ptで驚愕したけど、Div2はそこまで難しくない。
http://community.topcoder.com/stat?c=problem_statement&pm=12710

問題

２次元フィールド上でAliceとBobの初期位置および地形が与えられる。
AliceとBobは交互に隣接マスに移動する。
Aliceの移動経路が与えられるとき、BobがAliceから逃げ切れる(同一マスに止まらずに済む)かどうかを答えよ。

解法

Bの移動可能マスを毎ターン全列挙し、Aliceの移動が完了するまでに移動可能マスが０個になるかどうかを判定すればよい。
フィールドサイズH*W、移動ターンMに対し、計算量はO(HWM)なのでさほど問題ない。

	string check (vector <string> field, vector <string> moves) {
		bool okok[2][51][51];
		int ax,ay;
		int H=field.size();
		int W=field[0].size();
		ZERO(okok);
		
		int y,x,i,d;
		FOR(y,H) FOR(x,W) {
			if(field[y][x]=='A') ay=y,ax=x,field[y][x]='.';
			if(field[y][x]=='B') okok[0][y][x]=true,field[y][x]='.';
		}
		
		string M;
		FOR(x,moves.size()) M+=moves[x];
		
		FOR(i,M.size()) {
			int cur=i%2,tar=(i%2)^1;
			ZERO(okok[tar]);
			if(M[i]=='U') ay--;
			if(M[i]=='D') ay++;
			if(M[i]=='L') ax--;
			if(M[i]=='R') ax++;
			okok[cur][ay][ax]=false;
			
			FOR(y,H) FOR(x,W) {
				if(okok[cur][y][x]==false) continue;
				FOR(d,4) {
					int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
					int cx=x+dx[d],cy=y+dy[d];
					if(cx<0 || cy<0 || cx>=W || cy>=H) continue;
					if((cx!=ax || cy!=ay)&&field[cy][cx]=='.') okok[tar][cy][cx]=true;
				}
			}
		}
		
		FOR(y,H) FOR(x,W) if(okok[M.size()%2][y][x]) return "Bob wins";
		return "Alice wins";
	}

まとめ

Div2は意外とシンプルな問題。
普通だと計算量が心配だけど、H,W<=50、M<=2500と数値も小さいので大丈夫。