poj3126-prime+BFS

分析：

這題是在1000-10000之間，從一個素數變換到另一個素數。我們會想到先打印素數表，然後進行搜索。

另外，對素數的變換，我們應進行為的變換。采用queue來存。

代碼如下：

[cpp] 
#include<cstdio>  
#include<cmath>  
#include<queue>  
#include<cstring>  
using namespace std; 
 
int k,m; 
int a[4]={1,10,100,1000}; 
int visit[10000],prime[10000]; 
 
void get_prime()  //素數打表  
{ 
    int i,j; 
    for(i=2;i<=10000;i+=2){ 
      prime[i]=1; 
    } 
    int N=(int)sqrt(10000.0); 
    for(i=3;i<=N;i+=2){ 
     if(!prime[i]) 
    for(j=i*i;j<10000;j+=2*i) 
      prime[j]=1; 
    } 
} 
 
int prime_BFS() 
 { 
    queue<int>Q; 
    Q.push(k);   
    visit[k]=0; 
    while(!Q.empty()) 
    { 
        int s=Q.front(); 
        Q.pop(); 
        if(s==m) return visit[s]; 
        for(int i=0;i<4;i++) 
        {  
         for(int j=0;j<10;j++) 
          { 
           int x=s/(a[i]*10);    //這個變換不錯，參考牛人的代碼。   
           int y=s%a[i]; 
           int num=x*a[i]*10+j*a[i]+y; 
           if(num>1000&&visit[num]==-1&&!prime[num])   //num>1000排除了首位為零的。   
            {    
             Q.push(num); 
             visit[num]=visit[s]+1; 
            } 
          } 
        } 
    } 
   puts("Impossible"); 
} 
 
 int main() 
 {   
     int n; 
     get_prime(); 
     while(scanf("%d",&n)!=-1) 
       while(n--) 
       { 
         memset(visit,-1,sizeof(visit)); 
         scanf("%d%d",&k,&m);      
        // if(!prime[k]&&!prime[m]);  
        printf("%d\n",prime_BFS()); 
        } 
    return 0; 
} 
 
 
           
          

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

int k,m;
int a[4]={1,10,100,1000};
int visit[10000],prime[10000];

void get_prime()  //素數打表
{
 int i,j;
 for(i=2;i<=10000;i+=2){
   prime[i]=1;
 }
 int N=(int)sqrt(10000.0);
 for(i=3;i<=N;i+=2){
  if(!prime[i])
 for(j=i*i;j<10000;j+=2*i)
   prime[j]=1;
 }
}

int prime_BFS()
 {
 queue<int>Q;
 Q.push(k); 
 visit[k]=0;
    while(!Q.empty())
    {
        int s=Q.front();
        Q.pop();
  if(s==m) return visit[s];
        for(int i=0;i<4;i++)
        {
         for(int j=0;j<10;j++)
          {
           int x=s/(a[i]*10);    //這個變換不錯，參考牛人的代碼。
           int y=s%a[i];
           int num=x*a[i]*10+j*a[i]+y;
           if(num>1000&&visit[num]==-1&&!prime[num])   //num>1000排除了首位為零的。
            {  
     Q.push(num);
    visit[num]=visit[s]+1;
            }
          }
        }
 }
   puts("Impossible");
}

 int main()
 { 
  int n;
     get_prime();
     while(scanf("%d",&n)!=-1)
    while(n--)
       {
         memset(visit,-1,sizeof(visit));
         scanf("%d%d",&k,&m);    
        // if(!prime[k]&&!prime[m]);
        printf("%d\n",prime_BFS());
        }
    return 0;
}