Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-10-10Google Code Jam Japan 2011 決勝(復習)

Google Code Jam Japan 2011 決勝 D クローゼットルーム

| 23:02 | Google Code Jam Japan 2011 決勝 D クローゼットルーム - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 決勝 D クローゼットルーム - SRM diary(Sigmar) Google Code Jam Japan 2011 決勝 D クローゼットルーム - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

Smallのみ後で解いた

せいぜい8箇所くらいしか置けないし、あまりパターン数がないのでDFSで全探索するだけ


ソースコード

int rec(int d, vector <string> room, int str, int stc) {
	int h=room.size(), w=room[0].size();
	int clr[4][3]={{0,0,1},{0,0,-1},{0,1,0},{0,1,1}}, clc[4][3]={{0,1,0},{0,1,1},{0,0,-1},{0,0,1}};

	int res=0;
	if(d==h*w) {
		int dr[4]={0,0,1,-1}, dc[4]={1,-1,0,0};
		queue <pair <int, int> > q;
		int val[52][52];
		memset(val, -1, sizeof(val));
		q.push(make_pair(str, stc));
		val[str][stc]=0;
		while(!q.empty()) {
			int cr=q.front().first, cc=q.front().second; q.pop();
			res+=room[cr][cc]-'0';
			for(int i=0; i<4; i++) {
				int nr=cr+dr[i], nc=cc+dc[i];
				if(nr<0 || nr>=h || nc<0 || nc>=w) continue;
				if(room[nr][nc]=='X') continue;
				if(val[nr][nc]>=0) continue;
				q.push(make_pair(nr, nc));
				val[nr][nc]=val[cr][cc]+1;
			}
		}
		return res;
	}

	int cr=d/w, cc=d%w;
	for(int i=0; i<4; i++) {
		bool ok=true;
		for(int j=0; j<3; j++) {
			int nr=cr+clr[i][j], nc=cc+clc[i][j];
			if(nr<0 || nr>=h || nc<0 || nc>=w) ok=false;
			else if(room[nr][nc]=='X') ok=false;
			else if(j<2 && nr==str && nc==stc) ok=false;
		}
		if(!ok) continue;
		char save[2];
		for(int j=0; j<2; j++) {
			int nr=cr+clr[i][j], nc=cc+clc[i][j];
			save[j]=room[nr][nc];
			room[nr][nc]='X';
		}
		room[cr+clr[i][2]][cc+clc[i][2]]++;
		res=max(res, rec(d+1, room, str, stc));
		for(int j=0; j<2; j++) {
			int nr=cr+clr[i][j], nc=cc+clc[i][j];
			room[nr][nc]=save[j];
		}
		room[cr+clr[i][2]][cc+clc[i][2]]--;
	}
	res=max(res, rec(d+1, room, str, stc));

	return res;
}

int solve(vector <string> room) {
	int res=0;
	int h=room.size(), w=room[0].size();

	for(int i=0; i<h; i++) replace(room[i].begin(), room[i].end(), '.', '0');
	int str, stc;
	for(int i=0; i<h; i++) for(int j=0; j<w; j++) if(room[i][j]=='D') {
		str=i;
		stc=j;
		room[i][j]='0';
	}

	res=rec(0, room, str, stc);
	
	return res;
}

int main() {
	ifstream ifs("input.txt");
	ofstream ofs("output.txt");

	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		int H, W;
		ifs >> H >> W;
		vector <string> room(H);
		for(int i=0; i<H; i++) ifs >> room[i];
		int res=solve(room);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111010