POJ 3278 Catch That Cow：BFS 尋找最短抓捕路徑

題目大意

農夫與牛在一條數軸上，農夫初始位置 n，牛位置 k。農夫每步可移動到 x-1、x+1 或 x*2。求農夫抓到牛的最少步數。

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

BFS 天然適合求解無權圖的最短路徑。從起點開始，每一層擴展所有可達狀態，首次到達終點時的層數即為最短步數。

狀態擴展與剪枝

• 每個位置可產生 3 個子狀態：x-1、x+1、x*2。
• 為防止無限擴展導致超時，必須剪枝：
  • 位置不能小於 0。
  • 位置不宜過大，經驗上限設為 150000（因 k ≤ 100000，乘 2 後再回退足夠）。
  • 已訪問過的位置不再入隊（visit[] 數組）。
• 使用循環隊列實現 BFS，存儲節點的位置與步數。

代碼實現

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

struct Node {
    int pos, step;
    Node() {}
    Node(int p, int s) : pos(p), step(s) {}
};

Node que[1000000];
bool visit[200010];

int bfs(int n, int k) {
    if (n == k) return 0;
    memset(visit, false, sizeof(visit));
    int head = 0, tail = 0;
    que[tail++] = Node(n, 0);
    visit[n] = true;

    while (head != tail) {
        Node cur = que[head++];
        if (head >= 1000000) head = 0;

        int nextPos[3] = {cur.pos - 1, cur.pos + 1, cur.pos * 2};
        for (int i = 0; i < 3; i++) {
            int np = nextPos[i];
            if (np == k) return cur.step + 1;
            if (np >= 0 && np < 150005 && !visit[np]) {
                visit[np] = true;
                que[tail++] = Node(np, cur.step + 1);
                if (tail >= 1000000) tail = 0;
            }
        }
    }
    return -1; // 理論上不會到達
}

int main() {
    int n, k;
    cin >> n >> k;
    cout << bfs(n, k) << endl;
    return 0;
}

關鍵點總結

1. BFS 保證最短步數，因為同層節點步數相同，且先處理完前一層才進入下一層。
2. 剪枝條件 np < 150005 至關重要，否則狀態空間會爆炸導致 TLE。
3. 循環隊列避免了動態內存分配開銷，提高運行速度。