Codeforces #192 Div2 D "Biridian Forest"

問題

http://codeforces.com/contest/330/problem/D

訳

あなたはミケモンマスターになるための旅をしているミケモンブリーダーである。あなたは悪名高いブリディアンの森を抜けるのに苦労している。

・ブリディアンの森
ブリディアンの森は２次元のr行c列のマスで構成されたものである。それぞれのマスには木が生えているか、空である。空のマスには0人以上のミケモンブリーダーがいる。ミケモンブリーダーは（あなたを含め）木の生えているマスに入る事はできない。マスの１つは森の出口のマスとなっている。

初期のマスの情報は、あなたの初期位置と、出口のマスと、そして他のブリーダーの初期位置がある。

・動き
ブリーダーは（あなたも含め）森の中で行動をとる。一回の行動で、下記の中の１つの動きをする。

・待機する
・現在いるマスから隣のマスに移動する。（木のマスには移動できない）
・出口のマスにいるのなら、森から抜け出す。この行動はあなたしか行わない。

あなたが一回行動をとると、他のブリーダーが同時に一回行動をとる（どのように行動をとるかはブリーダーそれぞれで異なっていてもよい）

・ミケモンバトル
もし、あなたと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;
}