HDU 2717 BFS：三種操作最短路

題目

從整數 a 變到 b，允許操作：+1, -1, *2。求最少步數。a, b ≤ 200000。

關鍵優化

• a == b：答案 0。
• a > b：只能 -1，答案 a-b。
• a < b：BFS。狀態空間限制在 [0, 2*b]，因為超過 2*b 後再 *2 再 -1 絕不優於直接 -1。

BFS 代碼

const int MAXN = 200000;
int q[MAXN], dist[MAXN];
bool vis[MAXN];

while (cin >> n >> k) {
    if (n == k) { cout << 0 << '\n'; continue; }
    if (n > k) { cout << n-k << '\n'; continue; }
    memset(vis, 0, sizeof(vis));
    int head=0, tail=0;
    q[tail++] = n; vis[n]=1; dist[n]=0;
    while (head < tail && !vis[k]) {
        int u = q[head++];
        int v;
        v = u+1; if (v<=2*k && !vis[v]) { vis[v]=1; dist[v]=dist[u]+1; q[tail++]=v; }
        v = u-1; if (v>=0 && !vis[v]) { vis[v]=1; dist[v]=dist[u]+1; q[tail++]=v; }
        v = u*2; if (v<=2*k && !vis[v]) { vis[v]=1; dist[v]=dist[u]+1; q[tail++]=v; }
    }
    cout << dist[k] << '\n';
}

複雜度

狀態數 ≤ 2*k，邊數 ≤ 3×狀態數，O(k) 時間空間，k ≤ 100000 極快。