HDU 2717 Catch That Cow：BFS 最短路徑抓牛問題

問題描述

農夫 John 從數線上的位置 N (0 ≤ N ≤ 100,000) 出發，追捕停留在 K (0 ≤ K ≤ 100,000) 的牛。John 有兩種移動方式：

• 走路：從 X 移動到 X-1 或 X+1，耗時 1 分鐘。
• 傳送：從 X 移動到 2×X，耗時 1 分鐘。

求 John 抓到牛的最短時間。

解題思路：廣度優先搜索 (BFS)

狀態空間為 0~100,000 的整數點，每個點有三條邊：x-1, x+1, 2*x。所有邊權為 1，故 BFS 可求得最短步數。需注意邊界：傳送後位置不超過 100,000（或設稍大上限如 200,000 以防越界），且不小於 0。

優化剪枝

• 若 N ≥ K，只能走路後退，答案直接為 N-K。
• BFS 時用 vis[] 標記已訪問，避免重複入隊。
• 隊列存儲 (position, step)。

演算法流程

1. 若 N ≥ K，輸出 N-K 結束。
2. 初始化隊列，推入 (N, 0)，標記 vis[N]=true。
3. 循環：取出隊首 (cur, step)。
4. 生成三個下一狀態：cur-1, cur+1, cur*2。
5. 若任一等於 K，回傳 step+1。
6. 若在合法範圍內且未訪問，標記並入隊。

複雜度

• 時間：O(MAX_POS) ≈ O(100,000)。
• 空間：O(MAX_POS) 用於訪問陣列與隊列。

參考程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 200000;  // 足夠大的上限

int main() {
    int N, K;
    while (cin >> N >> K) {
        if (N >= K) {
            cout << N - K << '\n';
            continue;
        }
        vector vis(MAXV + 1, 0);
        queue> q;
        q.emplace(N, 0);
        vis[N] = 1;
        int ans = -1;
        while (!q.empty()) {
            auto [cur, step] = q.front(); q.pop();
            for (int nxt : {cur - 1, cur + 1, cur * 2}) {
                if (nxt == K) { ans = step + 1; break; }
                if (nxt < 0 || nxt > MAXV || vis[nxt]) continue;
                vis[nxt] = 1;
                q.emplace(nxt, step + 1);
            }
            if (ans != -1) break;
        }
        cout << ans << '\n';
    }
    return 0;
}

關鍵點總結

本題是經典的無權圖最短路問題，狀態轉移簡單，BFS 即可。注意邊界處理與 N≥K 的特判能大幅提升效率。