给定两个数a，b，每次只能变动a的其中一个数，变成的数也必须是素数，问最少经过几次可以变成b；

----------------------------------------------------------------------------------------------

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define MAXV 11000bool prime[MAXV];void init()//判断是否素数{    int i,j;    for(i=1000; i<=MAXV; i++)    {        for(j=2; j
          

q; int v,i,j,temp,vtemp,count[MAXV],t[4]; memset(dis,false,sizeof(dis)); memset(count,0,sizeof(count)); q.push(first); dis[first]=true; while(!q.empty()) { v=q.front(); q.pop(); t[0]=v/1000; t[1]=v%1000/100; t[2]=v%100/10; t[3]=v%10;// printf("%d %d %d %d",t[0],t[1],t[2],t[3]); for(j=0; j<4; j++) { temp=t[j]; for(i=0; i<10; i++) if(i!=temp) { t[j]=i; vtemp=t[0]*1000+t[1]*100+t[2]*10+t[3]; if(!dis[vtemp] && prime[vtemp]) { count[vtemp]=count[v]+1; dis[vtemp]=true; q.push(vtemp); } if(vtemp==last) return count[vtemp]; } t[j]=temp; } if(v==last) return count[v]; } return -1;}int main(){ int n,a,b,key; init(); scanf("%d",&n); while(n--) { scanf("%d%d",&a,&b); key=bfs(a,b); if(key!=-1) printf("%d\n",key); else printf("Impossible\n"); } return 0;}