C++

【定番コード】BFSで迷路の最短距離を求める。

ISO_C++_Logo

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」で関連する記事が探せます。迷路を解く問題を抜粋しました。

最後に

昨日の記事と本質的には同じですが、コードの見た目が異なるため別記事として紹介しました。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA