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

hamayanhamayan's blog

Conveyor [第五回 アルゴリズム実技検定 H]

https://atcoder.jp/contests/past202012-open/tasks/past202012_h

前提知識

  • bfs

解説

https://atcoder.jp/contests/past202012-open/submissions/22291073

今回の問題は到達性判定問題といえる。
この手の問題はbfsでの解法が有名であり、今回もbfsで解けないかということを考えてみる。
考えると、bfsで解けそうだとなる。

bfs

通常、bfsで到達性判定問題を解く場合は始点を一か所決めて、そこからbfsで到達できる終点を探していくことになる。
しかし、今回は終点が分かっていて、到達可能な始点を探すことが要求されている。
このような場合であっても、逆にたどっていくような感じでbfsで遷移していくことで到達可能かを判定できる。

移動を逆にたどっていくので、問題で提示されているルールも逆になる。
よってマスAからマスBに戻る場合にマスBに書かれている文字を考慮して戻れるかどうかを
チェックしながらbfsしていこう。

注意点として到達できない場合もあるので、そこはあとでxで塗っておこう。

dxdyテク

マス目上の隣接移動でdxdyを使ったテクがある。
座標差分を配列でまとめてそれを使うことで隣接マスへの移動をループで同一実装で行えるようにするもの。
dxdy配列の添え字を見ることでどの方向で移動したのが分かるため、これを判定にも使おう。

int H, W, ty, tx;
vector<string> S;
vector<string> ans;
enum { UP = 0, RIGHT, DOWN, LEFT };
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
queue<pair<int, int>> que;
void add(int x, int y) {
    que.push({ x, y });
    ans[y][x] = 'o';
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> ty >> tx;
    ty--; tx--;

    S.resize(H);
    ans.resize(H);
    rep(y, 0, H) {
        cin >> S[y];
        rep(x, 0, W) {
            if (S[y][x] == '#') ans[y] += "#";
            else ans[y] += "?";
        }
    }

    add(tx, ty);
    while (!que.empty()) {
        int x, y;
        tie(x, y) = que.front();
        que.pop();

        rep(d, 0, 4) {
            int xx = x + dx[d];
            int yy = y + dy[d];

            if (0 <= xx && xx < W && 0 <= yy && yy < H && ans[yy][xx] == '?' && S[yy][xx] != '#') {
                switch (S[yy][xx]) {
                    case '#': break;
                    case '.': add(xx, yy); break;
                    case '^': if (d == DOWN) add(xx, yy); break;
                    case 'v': if (d == UP) add(xx, yy); break;
                    case '>': if (d == LEFT) add(xx, yy); break;
                    case '<': if (d == RIGHT) add(xx, yy); break;
                }
            }
        }
    }

    rep(y, 0, H) rep(x, 0, W) if (ans[y][x] == '?') ans[y][x] = 'x';
    rep(y, 0, H) printf("%s\n", ans[y].c_str());
}