POJ 3126 Prime Path：BFS 在四位素數圖中尋找最短路徑

題目大意

給兩個四位素數 start, end。每步可修改一位數字，修改後必須仍為四位素數（首位不為 0）。求最少步數。多測試案例。不可達輸出 "Impossible"。

解法：BFS 在隱式圖上搜索

• 節點：所有四位素數 (1000~9999)。
• 邊：兩素數僅一位數字不同。
• 預處理：埃氏篩法生成所有四位素數 `isPrime[10000]`。
• BFS：從 start 開始，每次出隊嘗試修改 4 個位置上的數字 (0~9，千位 1~9)，若新數為素數且未訪問，入隊，距離 +1。直到到達 end 或隊列空。

關鍵代碼

#include 
#include 
#include 
using namespace std;

bool isPrime[10000];
int dist[10000];

void sieve() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i*i < 10000; ++i)
        if (isPrime[i])
            for (int j = i*i; j < 10000; j += i)
                isPrime[j] = false;
}

int bfs(int start, int end) {
    memset(dist, -1, sizeof(dist));
    queue q;
    q.push(start);
    dist[start] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == end) return dist[u];
        char s[5]; sprintf(s, "%04d", u);
        for (int pos = 0; pos < 4; ++pos) {
            char orig = s[pos];
            for (char d = '0'; d <= '9'; ++d) {
                if (pos == 0 && d == '0') continue;
                if (d == orig) continue;
                s[pos] = d;
                int v = atoi(s);
                if (isPrime[v] && dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
            s[pos] = orig;
        }
    }
    return -1;
}

int main() {
    sieve();
    int T; scanf("%d", &T);
    while (T--) {
        int a, b; scanf("%d%d", &a, &b);
        int ans = bfs(a, b);
        if (ans == -1) puts("Impossible");
        else printf("%d\n", ans);
    }
    return 0;
}

複雜度

• 素數篩：O(N log log N) ≈ 10⁴。
• BFS：節點 ≤ 1229 (四位素數個數)，每節點展開 4×9=36 邊，極快。

關鍵點

• **字符串操作生成鄰居**：`sprintf` + 修改字符 + `atoi` 簡潔高效。
• **千位不能為 0** 邏輯正確。
• **距離數組初始化 -1** 兼作訪問標記。

總結

POJ 3126 是「隱式圖 BFS」的經典例題。預處理素數表，運行時動態生成鄰居，BFS 保證最短路。代碼結構清晰，是圖論 BFS 入門佳作。