はまやんはまやんはまやん

hamayanhamayan's blog

Help the Princess! [JAG Practice Contest for ACM-ICPC Asia Regional 2016 : B]

問題

http://jag2016autumn.contest.atcoder.jp/tasks/icpc2016autumn_b

縦H,横Wの地図がある。
@ : 姫の初期位置
$ : 兵士の初期位置
% : ゴール
. : 通路
# : 壁
各ステップ、姫と兵士は隣接する通路に1マスだけ進むかその場にとどまるか選択できる。
姫と兵士が同じマスにいると姫は捕まる。
兵士がどんな動きをしても姫が脱出できるなら"Yes"、できないなら"No"

2 <= H, W <= 200

考察

1. マスの数が10^4か
2. まだBなので複雑な解法では無いかな・・・?
3. 簡単な解法だとDFS,BFSあたりだけれど
4. BFSで行けそうか?
5. いけそうでは?

6. 兵士は止まることもできるから、あるマスへの最短距離をそれぞれ求めておく -> bfs()
7. 姫は最短経路でマスを移動していくときに兵士に合わずにゴールまで行けるか -> bfs2()
8. WA(コーナーケース見落としてるぞ…)
9. 実装ミスだった

実装

http://jag2016autumn.contest.atcoder.jp/submissions/863821

int H, W;
string M[200];
 
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };
//-----------------------------------------------------------------
int enemy[200][200];
void bfs() {
	queue<int> que;
 
	rep(y, 0, H) rep(x, 0, W) if(M[y][x] == '$'){
		enemy[y][x] = 1;
		que.push(y * 1000 + x);
	}
 
	while (!que.empty()) {
		int q = que.front(); que.pop();
 
		int y = q / 1000;
		int x = q % 1000;
 
		rep(i, 0, 4) {
			int yy = y + dy[i];
			int xx = x + dx[i];
 
			if (yy < 0 || H <= yy) continue;
			if (xx < 0 || W <= xx) continue;
			if (M[yy][xx] == '#') continue;
			if (enemy[yy][xx]) continue;
 
			enemy[yy][xx] = enemy[y][x] + 1;
			que.push(yy * 1000 + xx);
		}
	}
}
//-----------------------------------------------------------------
int princess[200][200];
string bfs2() {
	queue<int> que;
 
	rep(y, 0, H) rep(x, 0, W) if (M[y][x] == '@') {
		princess[y][x] = 1;
		que.push(y * 1000 + x);
	}
 
	while (!que.empty()) {
		int q = que.front(); que.pop();
 
		int y = q / 1000;
		int x = q % 1000;
 
		rep(i, 0, 4) {
			int yy = y + dy[i];
			int xx = x + dx[i];
 
			if (yy < 0 || H <= yy) continue;
			if (xx < 0 || W <= xx) continue;
			if (M[yy][xx] == '#') continue;
			if (princess[yy][xx]) continue;
			if (0 < enemy[yy][xx] && enemy[yy][xx] <= princess[y][x] + 1) continue;
 
			princess[yy][xx] = princess[y][x] + 1;
			que.push(yy * 1000 + xx);
 
			if (M[yy][xx] == '%') return "Yes";
		}
	}
 
	return "No";
}
//-----------------------------------------------------------------
int main() {
	cin >> H >> W;
	rep(y, 0, H) cin >> M[y];
 
	bfs();
	cout << bfs2() << endl;
}