poj - 3126 - Prime Path

題意：從一個四位素數變到另一個四位素數，每次只能改到一個位的數字，且改動後仍是一個四位素數，問最少需要幾步。

——>>直接廣搜。

[cpp]  #include <cstdio>  
#include <cstring>  
#include <queue>  
 
using namespace std; 
 
const int maxn = 9999 + 10; 
int MAP[maxn], a, b, p[maxn], cnt; 
bool vis[maxn]; 
 
int translate(int x, int i, int j)      //把x的第i位變為j  
{ 
    int k, buf[4], ret = 0; 
    for(k = 0; k < 4; k++) 
    { 
        buf[k] = x % 10; 
        x /= 10; 
    } 
    buf[i] = j; 
    for(k = 3; k >= 0; k--) ret = ret * 10 + buf[k]; 
    return ret; 
} 
 
bool bs(int* A, int x, int y, int v)        //二分搜索  
{ 
    int m; 
    while(x < y) 
    { 
        m = x + (y - x) / 2; 
        if(A[m] == v) return 1; 
        else if(A[m] > v) y = m; 
        else x = m + 1; 
    } 
    return 0; 
} 
 
void get_prime()        //快速篩素數  
{ 
    memset(vis, 0, sizeof(vis)); 
    cnt = 0; 
    for(int i = 2; i <= 9999; i++) if(!vis[i]) 
    { 
        p[cnt++] = i; 
        for(int j = i; j <= 9999; j = j + i) vis[j] = 1; 
    } 
} 
 
void bfs() 
{ 
    if(a == b) return; 
    int temp, i, j; 
    queue<int> qu; 
    qu.push(a); 
    while(!qu.empty()) 
    { 
        temp = qu.front(); 
        qu.pop(); 
        for(i = 0; i < 4; i++) 
            for(j = 0; j < 10; j++) 
            { 
                if(j == 0 && (i == 0 || i == 3)) continue; 
                int tmp = translate(temp, i, j); 
                if(tmp % 2 == 0 || MAP[tmp] != -1) continue; 
                if(bs(p, 168, cnt, tmp)) 
                { 
                    MAP[tmp] = MAP[temp] + 1; 
                    if(tmp == b) return; 
                    qu.push(tmp); 
                } 
            } 
    } 
} 
 
int main() 
{ 
    int T; 
    get_prime(); 
    scanf("%d", &T); 
    while(T--) 
    { 
        scanf("%d%d", &a, &b); 
        memset(MAP, -1, sizeof(MAP)); 
        MAP[a] = 0; 
        bfs(); 
        printf("%d\n", MAP[b]); 
    } 
    return 0; 
}