//6266010 on_pku 3126 Accepted 732K 16MS G++ 2214B 2009-12-21 18:18:46 
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
using namespace std;
const int SIZE = 10000;
bool prime[SIZE];
int step[SIZE];
int base[4] = {1,10,100,1000};
int main()
{
        for(int i = 0; i < SIZE; i++)prime[i] = true;
        
        for(int i = 2; i < SIZE; i++){
                if(prime[i]){
                             for(int j = 2; i*j < SIZE; j++)
                                     prime[i*j] = false;             
                }        
        }
        
        int t,a,b,d[4];
        scanf("%d",&t);
        while(t--){
                   scanf("%d %d",&a,&b);
                   fill(step,step+SIZE,0);
                   queue<int>path;
                   path.push(a);
                   step[a] = 1;
                   while(!path.empty()){
                         int ori = path.front();
                         if(ori == b)break;
                         path.pop();
                         d[0] = ori%10;  d[1] = ori%100/10;
                         d[2] = ori%1000/100;  d[3] = ori/1000;
                         int newnum;
                         for(int i = 0; i < 10; i ++){                                                   
                                 newnum = ori - d[3]*1000 + i*1000;
                                 if(i != 0 && prime[newnum] && !step[newnum]){
                                      step[newnum] = step[ori] + 1;
                                      path.push(newnum);               
                                 } 
                                 for(int k = 0; k < 3; k++){
                                         newnum = ori - d[k]*base[k] + i*base[k];
                                         if(prime[newnum] && !step[newnum]){
                                              step[newnum] = step[ori] + 1;
                                              path.push(newnum);               
                                         }                               
                                 }  
                         }                     
                   }     
                   printf("%d\n",step[b]-1);
        }        
        return 0;
}

• 代码接近，贴出来抓个爪 o(∩_∩)o (3756) lsz 2011-05-07 20:36:58
• Re:代码较简洁，交流下 (2395) 2014302384 2015-08-17 14:07:02