Description

The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices. 
— It is a matter of security to change such things every now and then, to keep the enemy in the dark. 
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know! 
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door. 
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime! 
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds. 
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime. 

Now, the minister of finance, who had been eavesdropping, intervened. 
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound. 
— Hmm, in that case I need a computer program to minimize the cost. You don‘t know some very cheap software gurus, do you? 
— In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above. 

1033
1733
3733
3739
3779
8779
8179

The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

Input

Output

Sample Input

31033 81791373 80171033 1033

Sample Output

670

给出两个数s，e，都是素数，经过转化，将s转化为e的最小步数

规则，每一次只能修改一位，每次得到的数都是素数。

素数筛跑出1000到10000内的所有素数，如果其中两个素数只有一位不同，那么连接一条边，得到所有素数组合的图后用bfs直接搜索就可以

#include <cstdio>#include <cstring>#include <queue>#include <algorithm>using namespace std;int a[11000] , check[11000] , tot ;struct node{    int v , next ;}p[2000000];struct node1{    int u , t ;};queue <node1> que ;int head[10000] , cnt , flag[10000] ;void add(int u,int v){    p[cnt].v = v ;    p[cnt].next = head[u] ;    head[u] = cnt++ ;}void init(){    memset(check,0,sizeof(check));    memset(head,-1,sizeof(head));    tot = cnt = 0 ;    int i , j , k , num ;    for(i = 2 ; i <= 10000 ; i++)    {        if( !check[i] )            a[tot++] = i ;        for(j = 0 ; j < tot ; j++)        {            if(i*a[j] >= 10000)                break;            check[i*a[j]] = 1 ;            if( i%a[j] == 0 )                break;        }    }    for(i = 0 ; i < tot ; i++)        if( (a[i]/1000) ) break;    k = i ;    for(i = k ; i < tot ; i++)    {        for(j = k ; j < i ; j++)        {            num = 0 ;            if( a[i]%10 != a[j]%10 )                num++ ;            if( a[i]/10%10 != a[j]/10%10 )                num++ ;            if( a[i]/100%10 != a[j]/100%10 )                num++ ;            if( a[i]/1000%10 != a[j]/1000%10 )                num++ ;            if(num == 1)            {                add(i,j);                add(j,i);            }        }    }}int find1(int x){    int low = 0 , mid , high = tot-1 ;    while(low <= high)    {        mid = (low+high)/2 ;        if(a[mid] == x)            return mid ;        else if(a[mid] < x)            low = mid + 1 ;        else            high = mid -1 ;    }}int bfs(int s,int e){    memset(flag,0,sizeof(flag));    while( !que.empty() )        que.pop();    int i , j , v ;    node1 low , high ;    low.u = s ;    low.t = 0 ;    flag[s] = 1 ;    que.push(low);    while( !que.empty() )    {        low = que.front();        que.pop();        if( low.u == e )            return low.t ;        for(i = head[low.u] ; i != -1 ; i = p[i].next)        {            v = p[i].v ;            if( !flag[v] )            {                flag[v] = 1;                high.u = v ;                high.t = low.t + 1 ;                que.push(high);            }        }    }    return 0;}int main(){    int t , s , e ;    init();    scanf("%d", &t);    while(t--)    {        scanf("%d %d", &s, &e);        s = find1(s);        e = find1(e);        printf("%d\n", bfs(s,e) );    }    return 0;}

poj3126--Prime Path(广搜)