TopCoder SRM 563 Div2 Medium CoinsGameEasy

続いてDiv2 Medium。
Div2とはいえ、550ptなのでちょっと難しめ。
http://community.topcoder.com/stat?c=problem_statement&pm=12332

コインが２枚フィールド上にあるので、２枚同時に１マスずつ上下左右に動かした場合、１枚だけフィールド外に追い出すまでの最短操作回数を求める。

フィールドは20x20なので、コイン２枚でも20^4程度しかコインのパターンはない。
よって、DFSでちまちま探索していけばよい。
実装ゲーな問題。
コインが２枚重なったらその場でその移動方法は取れなくなることがポイント。

class CoinsGameEasy {
	public:
	int dist[21][21][21][21];
	int ds[21][21][21][21];
	int H,W,ms;
	char str[21][21];
	vector <string> B;
	void dfs(int cx0,int cy0, int cx1, int cy1) {
		if(dist[cx0][cy0][cx1][cy1]>=10) return;
		
		int dx[4]={1,-1,0,0};
		int dy[4]={0,0,1,-1};
			
		int loop,fc;
		FOR(loop,4) {
			int ncx0=cx0+dx[loop];
			int ncy0=cy0+dy[loop];
			int ncx1=cx1+dx[loop];
			int ncy1=cy1+dy[loop];
			fc=0;
			if(ncx0<0 || ncx0>=W || ncy0<0 || ncy0>=H) fc++;
			else {
				if(B[ncy0][ncx0]=='#') {
					ncx0=cx0;
					ncy0=cy0;
				}
			}
			if(ncx1<0 || ncx1>=W || ncy1<0 || ncy1>=H) fc++;
			else {
				if(B[ncy1][ncx1]=='#') {
					ncx1=cx1;
					ncy1=cy1;
				}
			}
			if(fc==1){
				ms=min(ms,dist[cx0][cy0][cx1][cy1]+1);	
				return;
			}
			if(fc==2) continue;
			if(ncx0==cx0 && ncy0==cy0 && ncx1==cx1 && ncy1==cy1) continue;
			if(ncx0==ncx1 && ncy0==ncy1) continue;
			if(dist[ncx0][ncy0][ncx1][ncy1]>dist[cx0][cy0][cx1][cy1]+1) {
				dist[ncx0][ncy0][ncx1][ncy1]=dist[cx0][cy0][cx1][cy1]+1;
				dfs(ncx0,ncy0,ncx1,ncy1);
			}
		}
		return;
	}
	
	int minimalSteps(vector <string> board) {
		H=board.size();
		W=board[0].size();
		B=board;
		FILL_INT(dist,1000000);
		int x,y;
		
		int nc=0;
		int cx[2],cy[2];
		FOR(y,H) FOR(x,W) {
			if(board[y][x]=='o') {
				cx[nc]=x;
				cy[nc]=y;
				nc++;
			}
		}
		ms=10000;
		dist[cx[0]][cy[0]][cx[1]][cy[1]]=0;
		dfs(cx[0],cy[0],cx[1],cy[1]);
		return (ms>10)?-1:ms;
	}
};

まとめ

解法自体はシンプルだけど、実装がちょっと入り組んで何度かミスしてしまった…。
今回はDiv1でもDiv2でもミス続きでひどい出来だな…。