给定两个数a，b，每次只能变动a的其中一个数，变成的数也必须是素数，问最少经过几次可以变成b；
----------------------------------------------------------------------------------------------
#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #include<stack> using namespace std; #define MAXV 11000 bool prime[MAXV]; void init()//判断是否素数 { int i,j; for(i=1000; i<=MAXV; i++) { for(j=2; j<i; j++) if(i%j==0) { prime[i]=false; break; } if(j==i) prime[i]=true; } } int bfs(int first,int last) { bool dis[MAXV]; queue <int>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 ",key); else printf("Impossible "); } return 0; }