ホーム > libalgo

グリッド上の幅優先探索

概要

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

計算量

$O(HW)$

使い方

gridBfs(g)
vector<string> などを渡す.距離の 2 次元配列を返す

実装

#include <bits/stdc++.h>
using namespace std;

using Weight = int;
using pii = pair<int, int>;
const Weight INF = 1000000000;
template <class Grid>
vector<vector<Weight>> gridBfs(const Grid &g, int si, int sj) {
    const int h = g.size(), w = g[0].size();

    // const int di[] = {0,-1,-1,-1,0,1,1,1};
    // const int dj[] = {1,1,0,-1,-1,-1,0,1};
    // const int len = 8;

    auto is_valid = [&](int i, int j) {
        if (i < 0 || i >= h || j < 0 || j >= w) return false;
        if (g[i][j] == '#') return false;
        return true;
    };

    auto get_next = [&](int ci, int cj) {
        static const pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        vector<pii> res;
        for (auto &d : dir) {
            int ni = ci + d.first;
            int nj = cj + d.second;
            if (is_valid(ni, nj)) res.emplace_back(ni, nj);
        }
        return res;
    };

    queue<pii> q;
    vector<vector<Weight>> d(h, vector<Weight>(w, INF));
    d[si][sj] = 0;
    q.emplace(si, sj);
    while (q.size()) {
        int ci, cj;
        tie(ci, cj) = q.front();
        q.pop();
        const vector<pii> next = get_next(ci, cj);
        for (auto &nx : next) {
            int ni, nj;
            tie(ni, nj) = nx;
            Weight nd = d[ci][cj] + 1;
            if (d[ni][nj] > nd) {
                d[ni][nj] = nd;
                q.emplace(ni, nj);
            }
        }
    }
    return d;
}