POJ 3126 Prime Path：四位素數圖上的 BFS 最短路徑

題目描述

給定兩個四位素數 start、target。每步可修改一位數字（千位不能為 0），且修改後必須仍為素數。求最少步數，或輸出 "Impossible"。

解題思路：BFS 在隱式圖上搜索

1. 預處理：埃氏篩法生成 10000 以內素數表 isPrime[]。
2. BFS 狀態：當前四位數。鄰居生成：枚舉 4 個位置，各嘗試 0-9（千位 1-9），若新數是素數且未訪問，入隊。
3. 距離數組 dist[] 記錄步數，找到目標即返回。

C++ 代碼實現

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

const int MAXN = 10000;
bool isPrime[MAXN];
int dist[MAXN];

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

int bfs(int s, int t) {
    if (s == t) return 0;
    memset(dist, -1, sizeof(dist));
    queue q;
    q.push(s); dist[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        int d[4] = {u/1000, u/100%10, u/10%10, u%10};
        for (int pos = 0; pos < 4; ++pos) {
            for (int dig = (pos==0?1:0); dig <= 9; ++dig) {
                if (dig == d[pos]) continue;
                int v = u;
                if (pos == 0) v = dig*1000 + u%1000;
                else if (pos == 1) v = u/1000*1000 + dig*100 + u%100;
                else if (pos == 2) v = u/100*100 + dig*10 + u%10;
                else v = u/10*10 + dig;
                if (isPrime[v] && dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    if (v == t) return dist[v];
                    q.push(v);
                }
            }
        }
    }
    return -1;
}

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;
}

關鍵點

• 千位不能為 0，生成鄰居時特別處理。
• BFS 保證最短路徑（邊權為 1）。
• 狀態空間僅 1061 個四位素數，BFS 極快。