グリッド上の幅優先探索

概要

グリッド上の幅優先探索．

計算量

$O(HW)$

使い方

grid_bfs(grid, start, wall): grid を文字 start を始点に wall は通らないで幅優先探索する．距離の 2 次元 vector を返す

実装

std::vector<std::vector<int>> grid_bfs(const std::vector<std::string> &g, char start, char wall) {
    const int INF = 1000000000;
    using pii = std::pair<int, int>;

    int h = g.size(), w = g[0].size();
    static const auto is_valid = [&](int i, int j) {
        if (i < 0 || i >= h || j < 0 || j >= w) return false;
        if (g[i][j] == wall) return false;
        return true;
    };

    static const pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    std::queue<pii> q;
    std::vector<std::vector<int>> d(h, std::vector<int>(w, INF));

    rep(i, h) rep(j, w) {
        if (g[i][j] == start) {
            d[i][j] = 0;
            q.emplace(i, j);
        }
    }

    while (q.size()) {
        int ci, cj;
        std::tie(ci, cj) = q.front();
        q.pop();
        for (auto &v : dir) {
            int ni = ci + v.first;
            int nj = cj + v.second;
            if (is_valid(ni, nj)) {
                int nd = d[ci][cj] + 1;
                if (d[ni][nj] > nd) {
                    d[ni][nj] = nd;
                    q.emplace(ni, nj);
                }
            }
        }
    }

    return d;
}