AtCoderABC C問題-幅優先探索を解説します．
ソースコードはこのようになりました(この書き方がいいのかはわからない).
#include <bits/stdc++.h>
int main() {
int R、 C、 sy、 sx、 gy、 gx;
std::cin >> R >> C >> sy >> sx >> gy >> gx;
--sy、 --sx、 --gy、 --gx;
/* 頂点を探索するときに使う、 {右、下、左、上} */
const int dx[4] = {1、 0、 -1、 0};
const int dy[4] = {0、 -1、 0、 1};
/* グリッドグラフの読み込み */
std::vector<std::string> stage(R);
for (int r = 0; r < R; ++r) std::cin >> stage[r];
/* 訪問予定の頂点を格納 */
std::queue<std::pair<int、 int>> que;
/* スタート地点からの距離 -1は未訪問を表す */
std::vector<std::vector> dist(R、 std::vector(C、 -1));
// スタート地点に(sy、 sx)を指定
dist[sy][sx] = 0;
que.push(std::make_pair(sy、 sx));
// BFS開始
while (!que.empty()) {
std::pair<int、 int> v = que.front();
que.pop();
for (int i = 0; i < 4; ++i) {
int y_cur = v.first; // 現在位置
int x_cur = v.second;
int y_next = y_cur + dy[i]; // 探索対象
int x_next = x_cur + dx[i];
if (stage[y_next][x_next] == '#') continue; // 壁の場合はskip
if (dist[y_next][x_next] != -1) continue; // 訪問済み
dist[y_next][x_next] = dist[y_cur][x_cur] + 1; // 距離の更新
que.push(std::make_pair(y_next、 x_next));
}
}
std::cout << dist[gy][gx] << std::endl;
return 0;
}
変数の定義・値の読み込み
グリッドグラフ上のスタート地点(sy、 sx)からゴール地点(gy、 gx)までの距離はいくつになるかという問題です．問題文にあるように幅優先探索(BFS)を用いて解きました．BFSに関してはこちらの記事がとても分かりやすかったです(感謝)．上記のソースコードも先ほどの記事で解説されている方法で実装しました．それでは上から順番に解説していきます．
まず変数を定義しています．R、Cはそれぞれグリッドグラフの行数と列数です．(sy、 sx)と(gy、 gx)はそれぞれスタート地点とゴール地点です．0-indexedにするため読みこんだ後にデクリメントしています．
dx、 dyは隣接する頂点を探索するときに用います．左から順番に右，下，左，上を表します．
int R、 C、 sy、 sx、 gy、 gx;
std::cin >> R >> C >> sy >> sx >> gy >> gx;
--sy、 --sx、 --gy、 --gx;
/* 頂点を探索するときに使う、 {右、下、左、上} */
const int dx[4] = {1、 0、 -1、 0};
const int dy[4] = {0、 -1、 0、 1};
/* 迷路の読み込み */
std::vector<std::string> stage(R);
for (int r = 0; r < R; ++r) std::cin >> stage[r];
キュートいうデータ構造を用いて訪問予定の頂点を加えていきます．頂点は(y、 x)のようにグリッドグラフ上のy座標とx座標をペアにして表しています．
distはスタート地点からの距離と頂点の状態を表します．-1は未訪問を表すとし，初期状態ではすべての頂点を-1で初期化しています．
次にスタート地点(sy、 sx)はスタート地点からの距離が0なのでdist[sy][sx] = 0とし一番初めの訪問予定の頂点としてqueに加えています．
/* 訪問予定の頂点を格納 */
std::queue<std::pair<int、 int>> que;
/* スタート地点からの距離 -1は未訪問を表す */
std::vector<std::vector> dist(R、 std::vector(C、 -1));
// スタート地点に(sy、 sx)を指定
dist[sy][sx] = 0;
que.push(std::make_pair(sy、 sx));
探索スタート
いよいよ探索をスタートします．キューの先頭から頂点を取り出し変数vに格納します．vの上下左右の頂点で未訪問の頂点をqueに加えます．このとき壁や訪問済みの頂点をqueに加えないようにif文で対策しています．
queが空になるまで探索を行い，最後に求める答えであるゴール地点までの距離dist[gy][gx]を出力しています．
// BFS開始
while (!que.empty()) {
std::pair<int、 int> v = que.front();
que.pop();
for (int i = 0; i < 4; ++i) {
int y_cur = v.first; // 現在位置
int x_cur = v.second;
int y_next = y_cur + dy[i]; // 探索対象
int x_next = x_cur + dx[i];
if (stage[y_next][x_next] == '#') continue; // 壁の場合はskip
if (dist[y_next][x_next] != -1) continue; // 訪問済みの場合はskip
dist[y_next][x_next] = dist[y_cur][x_cur] + 1; // 距離の更新
que.push(std::make_pair(y_next、 x_next));
}
}
std::cout << dist[gy][gx] << std::endl;
return 0;
}
以上で解説を終わります．
間違っているところや，意見がありましたら言っていただけると嬉しいです．