POJ 3278 Catch That Cow：BFS + 剪枝優化求最短步數

題目大意

農夫起點 N，目標牛位置 K（0 ≤ N, K ≤ 100,000）。農夫每步可：X+1、X-1、X*2。求到達 K 的最少步數。

BFS 基礎模型

狀態：位置 x。邊：三種移動，權重 1。標準 BFS 保證最短路。但搜索空間理論上無界（X*2 可無限增大），需剪枝限制範圍。

剪枝策略

1. 上界：當 x > K 時，x+1 和 x*2 必然遠離目標，只保留 x-1。
2. 下界：x < 0 非法，x-1 不入隊。
3. 訪問標記：vis[x] 防止重複入隊，空間開 200001 足夠（K≤100000，x*2 最大 200000）。

經剪枝，有效狀態數 ≤ 2*K，BFS 瞬間結束。

C++ 實現

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

const int MAX = 200000;
struct Node { int pos, step; };

int bfs(int N, int K) {
    if (N >= K) return N - K; // 只能往回走
    vector<int> vis(MAX + 1, -1);
    queue<Node> q;
    q.push({N, 0});
    vis[N] = 0;
    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        int x = cur.pos, s = cur.step;
        if (x == K) return s;
        // 三個方向
        int nx[3] = {x - 1, x + 1, x * 2};
        for (int i = 0; i < 3; i++) {
            int y = nx[i];
            if (y < 0 || y > MAX) continue;
            if (vis[y] != -1) continue;
            // 剪枝：x > K 時不往右/乘2
            if (x > K && (i == 1 || i == 2)) continue;
            vis[y] = s + 1;
            q.push({y, s + 1});
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K;
    while (cin >> N >> K) {
        cout << bfs(N, K) << "\n";
    }
    return 0;
}

關鍵優化細節

• 特判 N ≥ K：直接返回 N-K，避免 BFS 開銷。
• 環形隊列或 STL queue：數據量小，std::queue 足夠。
• 訪問數組用 -1 初始化：兼作距離記錄，省去額外 step 字段（但結構體更清晰）。

複雜度

延伸思考

• 雙向 BFS：從 N 和 K 同時擴展，相遇即停，進一步減半搜索空間。
• 0-1 BFS / Dijkstra：若三種移動代價不同（如 *2 代價 0），可用雙端隊列或優先隊列。
• 數學規律：本題實為「二進制位操作」最短路，存在 O(log K) 貪心解，但 BFS 通用性更強。

總結

POJ 3278 是「有界狀態空間 BFS + 極簡剪枝」的教科書級例題。核心洞見：目標單調時，反方向移動無意義。掌握此類剪枝直覺，能將指數級搜索壓縮為線性，是競賽與面試的關鍵技能。