幅優先探索（BFS）を使って迷路の最短経路を求める

幅優先探索のロジック

queueを用いて頂点の訪問判定を行う。queueの先頭の頂点において、たどれる他の頂点を探索し、訪問済みと判定しqueueに入れる。 この操作をqueueの中身が無くなるまで繰り返す。訪問済み判定と同時に頂点から何ステップかを記録することである地点からの最短経路を求めることができる。（辺の重みが全て等しい場合）

単純なグラフ入力に対して幅優先探索で最短経路を求めたもの↓

// 幅優先探索
int main() {
  // 頂点と辺の数
  int N,M;cin >> N >> M;

  vector<vector<int> > G(N);

  for (int i=0; i<M; i++) {
    int a,b;cin >> a >> b;
    G[a].push_back(b);
    G[b].push_back(a); // 無向グラフ
  }

  // 距離を管理するデータ構造
  vector<int> dist(N, -1);
  queue<int> q;

  // 初期条件
  dist[0] = 0;
  q.push(0);

  while(q.size()) { // queueがなくなるまで処理
    // 先頭の頂点を取り出す
    int top = q.front();
    q.pop();

    // その頂点がたどれる点を調べる
    for (int v : G[top]) {
      if (dist[v] != -1) continue; // すでにチェック済みだったらスルー

      // 距離をカウント
      dist[v] = dist[top] + 1;
      q.push(v);
    }
  }
}

迷路問題を解いてみる

応用して迷路のスタートからゴールまでの最短経路を求める https://atcoder.jp/contests/abc007/tasks/abc007_3

const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1};

int main() {
  int R,C;cin >> R >> C;
  int sy, sx;cin >> sy >> sx;
  int gy, gx;cin >> gy >> gx;
  vector<string> c(R);
  for (int i=0; i<R; i++) cin >> c[i];

  // 迷路と同じ2次元配列を用意する
  vector<vector<int> > dist(R, vector<int>(C, -1));
  // 座標として管理するのでpair型のqueue
  queue<pair<int, int> > q;

  // 初期条件
  // (sy, sx)が始点
  q.push(make_pair(sy-1, sx-1));
  dist[sy-1][sx-1] = 0;

  while (q.size()) {
    pair<int, int> top = q.front();
    q.pop();

    // 上下左右方向を探索
    for (int i=0; i<4; i++) {
      int ny = top.first + dy[i];
      int nx = top.second + dx[i];

      if (dist[ny][nx] != -1) continue; // 探索済みだったらスキップ
      if (c[ny][nx] == '#') continue; // 移動先が壁の場合スキップ
      dist[ny][nx] = dist[top.first][top.second] + 1;
      q.push(make_pair(ny, nx));
    }
  }
  cout << dist[gy-1][gx-1] << endl;
}

無事AC🙆‍♂️