【よくわかる解説】幅優先探索・BFS （グリッド上の）

問題

あなたは h x w サイズのグリッド上にいます。
グリッドは「通行可能」セル(.)、スタート位置(S)、ゴール位置(G)、および「障害物(#)」セルから構成されています。縦、横のみに移動できる。
幅優先探索(BFS)を使用して、スタート位置からゴール位置までの最短移動回数を答えてください。
到達不可能な場合は-1を出力してください。

入力

入力例1

4 5
....S
.#..#
..#.#
...G.

入力例2

3 3
.#G
###
S..

入力例3

6 4
...S
.###
....
###.
G.#.
....

解説動画

コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main() {
    int h, w;
    cin >> h >> w;
    vector s(h);
    rep(i, h) cin >> s[i];

    int si = 0, sj = 0, gi = 0, gj = 0;
    rep(i, h) {
        rep(j, w) {
            if (s[i][j] == 'S') {
                si = i;
                sj = j;
            }
            if (s[i][j] == 'G') {
                gi = i;
                gj = j;
            }
        }
    }

    vector dh = {1, 0, -1, 0};
    vector dw = {0, 1, 0, -1};

    queue<pair<int, int>> que;
    que.push({si, sj});
    vector<vector> dist(h, vector(w, -1));
    dist[si][sj] = 0;

    while(!que.empty()) {
        pair<int, int> now = que.front();
        que.pop();
        int now_i = now.first;
        int now_j = now.second;

        rep(dir, 4) {
            int next_i = now_i + dh[dir];
            int next_j = now_j + dw[dir];

            if (next_i < 0 || next_j < 0 || next_i >= h || next_j >= w) continue;
            if (s[next_i][next_j] == '#') continue;
            if (dist[next_i][next_j] != -1) continue;

            dist[next_i][next_j] = dist[now_i][now_j] + 1;
            que.push({next_i, next_j});
        }
    }

    cout << dist[gi][gj] << endl;

    return 0;
}