题目大意：给定两个4位的质数a和b，从a开始每次只能改变a的一个数字，并且改完后的a还是质数，求a最少经过几次变换能得到b.....
典型的最快求解问题
#include<iostream> #include<queue> #include<cstring> using namespace std; bool v[10001]; bool p[10001]; int vis[10001]; int prime[10000]; int sum; struct Node { int x,t; }; void getprime() { memset(p,0,sizeof(p)); int i,j; for(i=2;i<=100;i++) { for(j=i+i;j<=10000;j+=i) p[j]=true; } for(j=1000;j<=10000;j++) if(!p[j]) prime[sum++]=j; } void bfs(int s,int e) { int i; Node now,next; memset(p,0,sizeof(p)); queue<Node>q; now.x=s;now.t=0; q.push(now); for(i=0;i<sum;i++) vis[prime[i]]=99999; vis[s]=0; while(!q.empty()) { now=q.front(); if(now.x==e) break; q.pop(); int x1=now.x/1000; int x2=(now.x-x1*1000)/100; int x3=(now.x-x1*1000-x2*100)/10; int x4=now.x%10; for(int i=0;i<sum;i++)//遍历每一个4位素数 { int d=0; if(p[prime[i]]) continue; next.x=prime[i]; int y1=next.x/1000; if(x1==y1) d++; int y2=(next.x-y1*1000)/100; if(x2==y2) d++; int y3=(next.x-y1*1000-y2*100)/10; if(x3==y3) d++; int y4=next.x%10; if(x4==y4) d++; next.t=now.t+1; if(d==3)//看此素数是否之改变了一位 {
if(vis[prime[i]]>next.t)//这里需要减枝*（象征性的减一下 不减也可以）
{ vis[prime[i]]=next.t; p[prime[i]]=1; q.push(next);
} } } } if(vis[e]<99999) cout<<vis[e]<<endl; else cout<<"Impossible"<<endl; return ; } int main() { int t; int a,b; sum=0; getprime(); cin>>t; while(t--) { cin>>a>>b; bfs(a,b); } return 0; }