問題
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; }