C++でBFSを用いて最短距離を計算


現在位置と到着位置を知っていて、前後に1格移動することができて、前に5格移動して、最短距離のコードを求めます(1番の頂点から)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int d[] = {1, -1, 5};
int s, e;
int dis[10001];
queue<int> Q;

int main() {
    freopen("input.txt", "rt", stdin);
    cin >> s >> e;
    dis[s] = 0;
    Q.push(s);
    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();
        if (x == e) {
            cout << dis[x];
            return 0;
        }
        for (int i = 0; i < 3; i++) {
            int pos = x + d[i];
//          cout << "pos is : " << pos;
//          cout << '\n';
            if(pos < 0 || pos > 10000) continue;
            else if (dis[pos] == 0) {
                dis[pos] = dis[x] + 1;
                Q.push(pos);
            }
        }
    }
    return 0;
}
BFSを用いた場合,まず得られる結果値は最小到達距離である.そのため、特にリラックスする必要はありません.
  • dis[x]:位置xに何回移動したかを記録する
    ex)
    5 14