ABC 276

Table of Contents

E - Round Trip

https://atcoder.jp/contests/abc276/tasks/abc276_e

start から BFS をする。

といった具合に番号を振っていく。(番号が異なれば良いので上下左右と番号の対応が上記と違っても問題ない) 異なる番号が隣り合うところがあれば異なる経路で同じ場所にたどり着けるということなので Yes、そのような場所がなければ No を出力する。

sample 1 の場合の番号の付け方の例は以下のよう

 3   3   3  1
-1   3  -1  1
 2   0   1  1
 2  -1  -1  1

void solve() {
    int H, W;
    cin >> H >> W;
    vector<string> grid(H);
    rep(i, H) cin >> grid[i];

    int si, sj;
    rep(i, H) rep(j, W) if (grid[i][j] == 'S') si = i, sj = j;
    vvint mark(H, vint(W, -1));

    queue<pair<int, int>> q;
    q.push({si, sj});
    mark[si][sj] = 0;

    vint di = {0, 1, 0, -1};
    vint dj = {1, 0, -1, 0};

    while (q.size()) {
        auto [i, j] = q.front();
        q.pop();

        int c = mark[i][j];
        int start = c == 0;

        rep(d, 4) {
            if (start)
                c = d + 1;
            int ni = i + di[d], nj = j + dj[d];
            if (clamp(ni, 0, H - 1) != ni || clamp(nj, 0, W - 1) != nj)
                continue;
            if (grid[ni][nj] == '#')
                continue;
            int m = mark[ni][nj];
            if (m > 0 && m != c) {
                yesno(true);
                return;
            }
            if (m == -1) {
                mark[ni][nj] = c;
                q.push({ni, nj});
            }
        }
    }
    yesno(false);
}