kmjp's blog

競技プログラミング参加記です

TopCoder SRM 563 Div2 Medium CoinsGameEasy

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

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

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

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でもミス続きでひどい出来だな…。