ABC007 C問題 幅優先探索 解説

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;
}

以上で解説を終わります.
間違っているところや,意見がありましたら言っていただけると嬉しいです.

未分類の最新記事4件