グリッド上の幅優先探索(Grid-BFS)

目的

二次元格子状領域において、幅優先探索を行う。
また、要素xと要素yそれぞれが属するグループを併合することが可能。

オーダー

O(HW)

条件

grid_bfs(s, start, wall):= グリッド s 上にある文字 start からすべてのマスへの最短距離を求める。wall には移動できない。到達できるマスには最短距離、できないマスには -1 が格納される。

コード

vector<vector<int>> grid_bfs(vector<string> &s, char start, const string &wall = "#")
{
    const int vx[] = {0, 1, 0, -1}, vy[] = {1, 0, -1, 0};
    vector<vector<int>> min_cost(s.size(), vector<int>(s[0].size(), -1));
    queue<pair<int, int>> que;
    for (int i = 0; i < s.size(); i++)
    {
        for (int j = 0; j < s[i].size(); j++)
        {
            if (s[i][j] == start)
            {
                que.emplace(i, j);
                min_cost[i][j] = 0;
            }
        }
    }
    while (!que.empty())
    {
        auto p = que.front();
        que.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = p.first + vy[i], nx = p.second + vx[i];
            if (nx < 0 || ny < 0 || nx >= s[0].size() || ny >= s.size())
                continue;
            if (min_cost[ny][nx] != -1)
                continue;
            if (wall.find(s[ny][nx]) != string::npos)
                continue;
            min_cost[ny][nx] = min_cost[p.first][p.second] + 1;
            que.emplace(ny, nx);
        }
    }
    return min_cost;
}

コードテスト

ABC007-幅優先探索

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

typedef long long int ll;
#define REP(i, x) for (ll i = 0; i < (ll)(x); i++)

vector<vector<int>> grid_bfs(vector<string> &s, char start, const string &wall = "#")
{
    const int vx[] = {0, 1, 0, -1}, vy[] = {1, 0, -1, 0};
    vector<vector<int>> min_cost(s.size(), vector<int>(s[0].size(), -1));
    queue<pair<int, int>> que;
    for (int i = 0; i < s.size(); i++)
    {
        for (int j = 0; j < s[i].size(); j++)
        {
            if (s[i][j] == start)
            {
                que.emplace(i, j);
                min_cost[i][j] = 0;
            }
        }
    }
    while (!que.empty())
    {
        auto p = que.front();
        que.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = p.first + vy[i], nx = p.second + vx[i];
            if (nx < 0 || ny < 0 || nx >= s[0].size() || ny >= s.size())
                continue;
            if (min_cost[ny][nx] != -1)
                continue;
            if (wall.find(s[ny][nx]) != string::npos)
                continue;
            min_cost[ny][nx] = min_cost[p.first][p.second] + 1;
            que.emplace(ny, nx);
        }
    }
    return min_cost;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll R,C,sy,sx,gy,gx;
    cin >> R>>C>>sy>>sx>>gy>>gx;

    vector<string> c(R);
    REP(i,R){
        cin >> c.at(i);
    }

    c.at(sy - 1).at(sx - 1) = 's'; //スタート地点の文字置き換え

    auto ans = grid_bfs(c, 's', "#");
    cout << ans.at(gy - 1).at(gx - 1) << endl;
}

出典

ei1333.github.io