Codeforces #192 Div2 D "Biridian Forest"
問題
http://codeforces.com/contest/330/problem/D
訳
あなたはミケモンマスターになるための旅をしているミケモンブリーダーである。あなたは悪名高いブリディアンの森を抜けるのに苦労している。
・ブリディアンの森
ブリディアンの森は2次元のr行c列のマスで構成されたものである。それぞれのマスには木が生えているか、空である。空のマスには0人以上のミケモンブリーダーがいる。ミケモンブリーダーは(あなたを含め)木の生えているマスに入る事はできない。マスの1つは森の出口のマスとなっている。
初期のマスの情報は、あなたの初期位置と、出口のマスと、そして他のブリーダーの初期位置がある。
・動き
ブリーダーは(あなたも含め)森の中で行動をとる。一回の行動で、下記の中の1つの動きをする。
・待機する ・現在いるマスから隣のマスに移動する。(木のマスには移動できない) ・出口のマスにいるのなら、森から抜け出す。この行動はあなたしか行わない。
あなたが一回行動をとると、他のブリーダーが同時に一回行動をとる(どのように行動をとるかはブリーダーそれぞれで異なっていてもよい)
・ミケモンバトル
もし、あなたとt人のミケモンブリーダーが同じマスに入ったとき、ちょうどt回ミケモンバトルが起こる。バトルの後、彼らは彼らのミケモンをミケモンセンターで癒すため、森から立ち去る。
あなたが森から脱出した後は、即座に他のブリーダーが出口マスに移動したとしても、ミケモンバトルはそれ以上起こらない。それから、ミケモンバトルは、あなたと他のブリーダーとの間でしか起こらない(たとえ他のブリーダーが同じマスに同時に入ったとしてもバトルは起こらない)。
・あなたの目的
あなたは森から脱出したい。そうするために、あなたは複数の行動をとり、最後の種類の動きを行う(つまり出口マス上で抜け出す動作)。あなたは既に森を脱出するまでに、どう行動をとるかについて、あなたのブログに乗せていた。あなたはブログに乗せたものに忠実に動くことになる。
・他のブリーダーの目的
あなたがブログに行動について書いたことにより、他のブリーダーにあなたがどう行動をとるか、確実に分かっている。彼らは可能であれば、あなたとミケモンバトルが起きるよう、行動をとるだろう。そうでなければ、彼らは待機している。
・課題
最善の行動をとり、森から脱出するまでのミケモンバトルの回数を最小化し、それを出力せよ。
制約
1 <= r, c <= 1000
考えた事
出口までの最短距離が、主人公よりも近いか同じブリーダーは、出口で待ち伏せする事により、ミケモンバトルを起こす事ができる。他のブリーダーにとって最善の行動はこのように出口で待ち伏せする事である。よって、主人公の最善の行動は、最短距離を歩く事である。
ゴールを起点としたBFSなどで、最短距離が主人公と同じかそれ以下のブリーダーの数を数えればよい。
ソースコード
int H, W; vector<string> field; bool chk[1010][1010]; class S{ public: S( int _c, int _x, int _y ): c(_c), x(_x), y(_y){} int c, x, y; }; int main() { cin >> H >> W; for( int i = 0; i < H; i++ ){ string line; cin >> line; field.push_back( line ); } int sx = -1, sy = -1; for( int y = 0; y < H; y++ ){ for( int x = 0; x < W; x++ ){ if( field[y][x] == 'E' ){ sx = x, sy = y; } } } int ans = 0; memset( chk, false, sizeof(chk) ); queue<S> que; que.push( S( 0, sx, sy ) ); field[sy][sx] = '0'; chk[sy][sx] = true; int playerTurn = (int)1e9; while( !que.empty() ){ // キューからポップ int c = que.front().c; int x = que.front().x; int y = que.front().y; que.pop(); // プレイヤーターンより大きいものだ if( playerTurn < c ){ // 何もしない continue; } // プレイヤーだった if( field[y][x] == 'S' ){ // プレイヤーターンを設定 playerTurn = c; } // ブリーダーだった else{ // ansに加算 ans += field[y][x] - '0'; } int dx[] = { 0, 0, -1, 1 }; int dy[] = { -1, 1, 0, 0 }; // 4方のマスを追加 for( int d = 0; d < 4; d++ ){ int tx = x + dx[d]; int ty = y + dy[d]; if( tx < 0 || W <= tx || ty < 0 || H <= ty ) continue; // ツリーなら何もしない if( field[ty][tx] == 'T' ) continue; // チェック済みならなにもしない if( chk[ty][tx] ) continue; // チェック済みにしておく chk[ty][tx] = true; // ターンを加算してキューに追加 que.push( S( c+1, tx, ty ) ); } } cout << ans << endl; }