【題目敘述】https://vjudge.net/problem/POJ-3278
【解題想法】BFS
- 在數線座標上，每單位時間可以從點 x 移動到 x + 1、x – 1 或 2 * x。
- dis[ ]：紀錄走到每個點的最短距離。初始值設為INF，表示該點未曾走訪。
- (Line-18/22/26) 在不超出界限的情況下測試三種移動的可能性。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 100000;
int n, k, dis[maxn+1], now;
queue <int> q;
int main() {
while (cin >> n >> k){
memset(dis, 0x3F, sizeof(dis));
q.push(n);
dis[n] = 0;
while (!q.empty()){
now = q.front();
q.pop();
if (now+1 <= maxn && dis[now]+1 < dis[now+1]){
dis[now+1] = dis[now]+1;
q.push(now+1);
}
if (now-1 >= 0 && dis[now]+1 < dis[now-1]){
dis[now-1] = dis[now]+1;
q.push(now-1);
}
if (now*2 <= maxn && dis[now]+1 < dis[now*2]){
dis[now*2] = dis[now]+1;
q.push(now*2);
}
}
cout << dis[k] << "\n";
}
}