题目链接：

题意：每组测试案例给出两个数a，b，从数字a开始，每次只改变当前数中的一位数，使之仍为一个素数，问经过多少步骤能够得到数字b。

代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 int cnt[10000]; 8 bool vis[10000]; 9 bool prime[10000];10 void init()11 {12     int key;13     for (int i = 1000;i <= 9999;i++){14         key = 1;15         for (int j = 2;j < i;j++){16             if (i%j == 0){17                 key = 0;18                 break;19             }20         }21         if (key)22             prime[i] = true;23     }24 }25 26 int bfs(int snum,int endnum)27 {28     memset(vis,0,sizeof(vis));29     memset(cnt,0,sizeof(cnt));30     queue
           
            q;31 vis[snum]=1;32 q.push(snum);33 int bit[10];34 while(!q.empty()){35 int temp=q.front();36 q.pop();37 if(temp==endnum)38 return cnt[endnum];39 bit[1]=temp/1000; bit[2]=(temp/100)%10; bit[3]=(temp/10)%10; bit[4]=temp%10;40 for(int bi=1;bi<=4;bi++){41 int temp1=bit[bi];42 for(int i=0;i<10;i++){43 if(bi==1 && i==0)44 continue;45 bit[bi]=i;46 int sum=bit[1]*1000+bit[2]*100+bit[3]*10+bit[4];47 if(prime[sum]&&(!vis[sum])){48 vis[sum]=1;49 cnt[sum]=cnt[temp]+1;50 q.push(sum);51 }52 }53 bit[bi]=temp1;54 }55 }56 return -1;57 }58 int main()59 {60 init();61 int snum,endnum,ans,T;62 scanf("%d",&T);63 while(T--){64 scanf("%d%d",&snum,&endnum);65 ans=bfs(snum,endnum);66 if(ans==-1)67 printf("Impossible\n");68 else69 printf("%d\n",ans);70 }71 return 0;72 }