Prime Path (BFS) - 四位素數變換最短路徑

問題描述

給定兩個四位素數 start 和 target (1000~9999)。每步可修改一位數字 (千位不能為 0)，且修改後必須仍為素數。求從 start 到 target 的最少步數。若無法到達輸出 "Impossible"。多測試案例 (≤ 100)。

解法：BFS 在素數圖上尋找最短路徑

1. 預處理：篩法 (埃拉托斯特尼篩) 求出所有四位素數 (1000~9999)，存入 is_prime[] 布爾數組。
2. BFS：狀態 = 當前四位數。從 start 開始，每步枚舉 4 個位置 × 10 個數字 (0-9)，生成新數 next。條件：next 為素數、未訪問、千位非 0。入隊記錄步數。首次到達 target 即為答案。
3. 優化：千位只能換 1,3,7,9 (素數個位特性)；但直接枚舉 0-9 並查 is_prime 也極快 (節點數 ~1000，邊數 ~4000)。

參考代碼

#include 
using namespace std;

const int MAXN = 10000;
bool is_prime[MAXN];
bool vis[MAXN];

struct Node { int num, step; };

void sieve() {
    fill(is_prime, is_prime+MAXN, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i*i < MAXN; i++)
        if (is_prime[i])
            for (int j = i*i; j < MAXN; j += i)
                is_prime[j] = false;
}

int bfs(int start, int target) {
    if (start == target) return 0;
    memset(vis, 0, sizeof(vis));
    queue q;
    q.push({start, 0});
    vis[start] = true;
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        int d[4];
        int tmp = cur.num;
        for (int i = 3; i >= 0; i--) { d[i] = tmp % 10; tmp /= 10; }
        for (int pos = 0; pos < 4; pos++) {
            for (int dig = 0; dig <= 9; dig++) {
                if (dig == d[pos]) continue;
                if (pos == 0 && dig == 0) continue; // 千位非0
                int next = 0;
                for (int i = 0; i < 4; i++)
                    next = next * 10 + (i == pos ? dig : d[i]);
                if (is_prime[next] && !vis[next]) {
                    if (next == target) return cur.step + 1;
                    vis[next] = true;
                    q.push({next, cur.step + 1});
                }
            }
        }
    }
    return -1; // Impossible
}

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

複雜度

• 篩法預處理：O(MAXN log log MAXN) ≈ 10⁴，一次性。
• BFS：節點 ≤ 1061 (四位素數個數)，每節點擴展 ≤ 36 邊。單查詢 O(1000) 極快。
• 100 組測試總時間 < 10ms。

關鍵細節

• 千位不能為 0，生成新數時檢查 pos==0 && dig==0 跳過。
• 入隊即標記 vis，防止重複入隊。
• 起點 = 終點直接返回 0。
• 輸出 "Impossible" 大小寫敏感。