Ito Campus [九州大学プログラミングコンテスト2018 C]

https://beta.atcoder.jp/contests/qupc2018/tasks/qupc2018_c

前提知識

• BFS

解説

https://beta.atcoder.jp/contests/qupc2018/submissions/3436552

二回bfsをして答える。
　
関数bfs1
イノシシがX回の移動で移動できるマスにngフラグを立てる。
よくある手法なのだが、始点が複数個あり、一気にbfsをするテクというのがある。
これは、ただbfsをするのではなく、1回移動、2回移動、3回移動、…をまとめて行うテクである。
i回目の移動をする場合は、キューにi-1回の移動で移動できる座標が入っている。
ここから、1回移動して、まだ訪れていない座標を次のキューに入れる。
これをX回繰り返すことで、一気にbfsができる。
0回移動、1回移動、2回移動、…で訪れていない座標だけキューに入れられるので、ならしO(HW)で間に合う。
　
関数bfs2
通れない座標について計算できたので、あとは始点から終点までそこを通らない最短距離をbfsで求める。
一般的なbfsをすればいい。

int H, W, X;
string S[1010];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
int ng[1010][1010];
void bfs1() {
    queue<pair<int, int>> que;
    rep(y, 0, H) rep(x, 0, W) if (S[y][x] == '@') {
        que.push({ x,y });
        ng[y][x] = 1;
    }
 
    rep(_, 0, X) {
        queue<pair<int, int>> que2;
        while (!que.empty()) {
            auto q = que.front(); que.pop();
 
            int x = q.first;
            int y = q.second;
            rep(i, 0, 4) {
                int xx = x + dx[i];
                int yy = y + dy[i];
                if (0 <= xx and xx < W and 0 <= y and yy < H) {
                    if (S[yy][xx] == '#') continue;
                    if (!ng[yy][xx]) {
                        que2.push({ xx, yy });
                        ng[yy][xx] = 1;
                    }
                }
            }
        }
        swap(que, que2);
    }
}
//---------------------------------------------------------------------------------------------------
int d[1010][1010];
int bfs2() {
    rep(y, 0, H) rep(x, 0, W) d[y][x] = -1;
 
    queue<pair<int, int>> que;
    rep(y, 0, H) rep(x, 0, W) if (S[y][x] == 'S') {
        que.push({ x,y });
        d[y][x] = 0;
    }
 
    while (!que.empty()) {
        auto q = que.front(); que.pop();
 
        int x = q.first;
        int y = q.second;
 
        if (S[y][x] == 'G') return d[y][x];
 
        rep(i, 0, 4) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (0 <= xx and xx < W and 0 <= y and yy < H) {
                if (S[yy][xx] == '#') continue;
                if (d[yy][xx] < 0 and !ng[yy][xx]) {
                    que.push({ xx, yy });
                    d[yy][xx] = d[y][x] + 1;
                }
            }
        }
    }
 
    return -1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> X;
    rep(y, 0, H) cin >> S[y];
 
    bfs1();
    cout << bfs2() << endl;
}