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を用いた場合,まず得られる結果値は最小到達距離である.そのため、特にリラックスする必要はありません.ex)
5 14
Reference
この問題について(C++でBFSを用いて最短距離を計算), 我々は、より多くの情報をここで見つけました https://velog.io/@juwon9733/BFS를-활용한-최단-거리-계산-in-Cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol