大致题意：
给定两个四位素数a b，要求把a变换到b
变换的过程要保证 每次变换出来的数都是一个 四位素数，而且当前这步的变换所得的素数 与 前一步得到的素数 只能有一个位不同，而且每步得到的素数都不能重复。
每一个a都可以找到一个b，所以都会有答案，题目中如果找不到输出impossible这句话可以无视了。
下面是代码：
#include <stdio.h> #include <string.h> #include <queue> using namespace std; struct node { int pr,cut; bool operator > (const node &a) const { return cut >a.cut; } }dc,du; bool boo[10000],vis[10000]; int main() { int i,j,k,t,a,b,po[4],pe[4],sum; const int be[4]={1,10,100,1000}; memset(boo,0,sizeof(boo)); for( i=2; i <= 100; i++ ) //素数筛 { for( k=i*2; k <10000; k += i ) { boo[k] = 1; } } scanf("%d",&t); while(t--) { scanf("%d%d",&a,&b); memset(vis,0,sizeof(vis)); du.pr=a; vis[a]=1; du.cut=0; priority_queue <struct node ,vector <struct node> ,greater <struct node> >q; q.push(du); while(!q.empty()) { du=q.top(); q.pop(); if(du.pr==b) { break; } for(i=0;i<4;i++) { po[i]=du.pr; du.pr/=10; } for(i=0;i<4;i++) { memcpy(pe,po,sizeof(po)); for(j=0;j<10;j++) { pe[i]=j; sum=0; for(k=0;k<4;k++) { sum+=pe[k]*be[k]; } if(sum>1000&&!boo[sum]&&!vis[sum]) { vis[sum]=1; dc.pr=sum; dc.cut=du.cut+1; q.push(dc); } } } } printf("%d\n",du.cut); } return 0; }
转载于:https://www.cnblogs.com/lin375691011/p/3996754.html
相关资源：JAVA上百实例源码以及开源项目