迷路の問題を幅優先探索で解く

Jan 30, 2021 08:00 ·

問題解決能力を鍛える!アルゴリズムとデータ構造 を少しずつ読み進めている。

13 章「グラフ(1):グラフ探索」の章末問題、

1.2.2 節で見たような迷路について、迷路のサイズを H x W として、スタートからゴールまで辿り着く最短路を O(HW) で求めるアルゴリズムを設計してください。

をなんとか解くことができた。

#include <iostream>
#include <vector>
#include <queue>
using namespace std; 
using Graph = vector<vector<int>>; 

struct Position
{

    int row, col;

}; 

bool is_in_range(Position &pos, int row_size, int col_size)
{

    if ((pos.row < 0) || (pos.row > row_size - 1))
    {
        return false;
    }
    if ((pos.col < 0) || (pos.col > col_size - 1))
    {
        return false;
    }
    return true;

}

int bfs(vector<vector<char>> maze, int row_size, int col_size, Position cursor)
{

    vector<vector<bool>> VISITED{}; // 探索済みを格納する配列
    vector<vector<int>> depth{};    // 始点から各頂点までの距離を格納する配列

    // 探索済みを格納する配列と、始点から各頂点までの距離を格納する配列を初期化する
    for (int row = 0; row < row_size * col_size; row++)
    {
        VISITED.push_back({});
        depth.push_back({});
    }
    for (int row = 0; row < row_size; row++)
    {
        for (int col = 0; col < col_size; col++)
        {
            VISITED[row].push_back(false);
            depth[row].push_back(-1);
        }
    }

    queue<Position> que;
    depth[cursor.row][cursor.col] = 0;
    que.push(cursor);

    int d = 0;
    while (!que.empty())
    {
        Position pos = que.front();
        que.pop();
        if (maze[pos.row][pos.col] == 'g')
        {
            return depth[pos.row][pos.col];
        }

        // 移動量 ( 上、右、下、左 )
        vector<int> nx = {0, 1, 0, -1};
        vector<int> ny = {-1, 0, 1, 0};

        for (int i = 0; i < nx.size(); i++)
        {
            // next に移動後の頂点を代入する
            Position next = {pos.row + ny[i], pos.col + nx[i]};
            if (is_in_range(next, row_size, col_size))
            {
                // 移動後の頂点が障害物または訪問済みではない場合、
                // 始点から移動後までの距離に、始点から移動前の距離に 1 を足したものを格納する
                if ((maze[next.row][next.col] != 'x') && !VISITED[next.row][next.col])
                {
                    depth[next.row][next.col] = depth[pos.row][pos.col] + 1;
                    VISITED[next.row][next.col] = true;
                    que.push(next);
                }
            }
        }
    }
    return -1;

}

int main()
{

    // o:通路
    // x:障害物
    // g:ゴール

    vector<vector<char>> maze1 = {
        {'o', 'o', 'g'},
        {'o', 'x', 'o'},
        {'o', 'x', 'o'},
        {'o', 'o', 'o'},
    };
    int depth1 = bfs(maze1, maze1.size(), maze1[0].size(), {0, 0});
    cout << depth1 << endl; // 2

    vector<vector<char>> maze2 = {
        {'o', 'x', 'g'},
        {'o', 'x', 'o'},
        {'o', 'x', 'o'},
        {'o', 'o', 'o'},
    };
    int depth2 = bfs(maze2, maze2.size(), maze2[0].size(), {0, 0});
    cout << depth2 << endl; // 8

}