問題解決能力を鍛える！アルゴリズムとデータ構造 を少しずつ読み進めている。
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
}