BFS（幅優先探索：Breadth-First search）で迷路のスタートからゴールまでの最短距離を求めることができます。そのコードを整理しました。
定番コードの紹介
グリッドの表現と入力
グリッドはグラフと比較するといくつかの入力フォーマットがあります。
ABC007C問題では、迷路の大きさ、スタート地点、ゴール地点、迷路情報を入力とします。
7 8
2 2
4 5
########
#......#
#.######
#..#...#
#..##..#
##.....#
########ABC276E問題では、迷路の大きさ、迷路情報を入力とします。スタート地点を ’S’ としています。
4 4
....
#.#.
.S..
.##.入力に多様性があり、コードの一本化は難しいようです。
BFSにより最短距離を求める。
キューを使って、スタート地点からゴール地点への最短距離を求めます。最短距離は配列 dist に格納します。キューが空になってループを抜けても dist の値が -1 の場合は、たどり着けないことを意味します。
- 迷路の情報は、2次元配列 maze に格納しています。
- グリッドの上下左右移動の計算を楽にするために差分を配列 dx と dy に定義しておきます。この配列は再利用できます。
- スタート地点をキューに格納して距離を 0 にします。
- キューを使って、起点となる頂点から距離が短い順に配列
distを更新します（5ー14行目）。
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
queue<pair<int, int>> que;
vector<vector<int>> dist(r, vector(c, -1));
que.push(make_pair(sx, sy));
dist[sy][sx] = 0;
while (!que.empty()) {
pair<int, int> now = que.front();
que.pop();
int now_x = now.first;
int now_y = now.second;
for (int i = 0; i < 4; ++i) {
int next_x = now_x + dx[i];
int next_y = now_y + dy[i];
if ((0 <= next_x) && (next_x < c) && (0 <= next_y) &&
(next_y < r) && (dist[next_y][next_x] == -1) &&
(maze[next_y][next_x] == '.')) {
que.push(make_pair(next_x, next_y));
dist[next_y][next_x] = dist[now_y][now_x] + 1;
}
}
}
cout << dist[gy][gx] << endl;紹介した定番コードを使った動作するコードを紹介します。ABC007C問題の回答となります。
- $n$ 頂点、$m$ 辺の有向グラフを読み込みます。
- BFSで頂点1から、他の頂点への距離を求めます。
- 最後に頂点1から頂点 $n$ への最短距離を出力します。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int r, c;
cin >> r >> c;
int sy, sx;
cin >> sy >> sx;
--sy;
--sx;
int gy, gx;
cin >> gy >> gx;
--gy;
--gx;
vector<string> maze(r);
for (int i = 0; i < r; ++i) {
cin >> maze[i];
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
queue<pair<int, int>> que;
vector<vector<int>> dist(r, vector(c, -1));
que.push(make_pair(sx, sy));
dist[sy][sx] = 0;
while (!que.empty()) {
pair<int, int> now = que.front();
que.pop();
int now_x = now.first;
int now_y = now.second;
for (int i = 0; i < 4; ++i) {
int next_x = now_x + dx[i];
int next_y = now_y + dy[i];
if ((0 <= next_x) && (next_x < c) && (0 <= next_y) &&
(next_y < r) && (dist[next_y][next_x] == -1) &&
(maze[next_y][next_x] == '.')) {
que.push(make_pair(next_x, next_y));
dist[next_y][next_x] = dist[now_y][now_x] + 1;
}
}
}
cout << dist[gy][gx] << endl;
return 0;
}BFSを使う問題
タグ「BFS」で関連する記事が探せます。迷路を解く問題を抜粋しました。
最後に
昨日の記事と本質的には同じですが、コードの見た目が異なるため別記事として紹介しました。
