题目大意：给你两个素数判断从这个素数，到另一个素数最少改变几次，每次改变都要是素数
思路：使用bfs 数字是四位数，判断所有可以变成的数字是不是素数。变成另一个素数后输出步数即可
值得一提的是，需要首先打好一个素数表，不然很费时
#include<stdio.h> #include<string.h> int n,m; int book[10000];//标记数组，这个数是否变过 int z[10000];//存储一个数是不是素数 int isprimer(int k){//判断其是不是素数 int i; for(i=2;i*i<=k;i++){ if(k%i==0) return 0; } return 1; } void dfs(); int change(int a,int k,int l){//把一个数变成另一个数 switch(k){ case 1:{ return (a-a+l); break; } case 2:{ return (a-(a0)/10*10+l*10); break; } case 3:{ return (a-(a/100)*100+l*100); break; } case 4:{ return (a00+l*1000); break; } } } int main(void) { int numer; scanf("%d",&numer); int i; for(i=1000;i<10000;i++){ z[i]=isprimer(i); } while(numer--){ scanf("%d%d",&n,&m); dfs(); } return 0; } void dfs(){ memset(book,0,sizeof(book)); struct node{ int num; int step; }q[100005]; int head=0; int tail=1; book[n]=1; q[head].num=n; q[head].step=0; while(head<tail){ if(q[head].num==m){//判断是否是另一个数 printf("%d\n",q[head].step); return ; } int i; int t=q[head].num; for(i=0;i<10;i++){//下面是改变这个数 int temp=change(t,1,i); if(!book[temp]&&z[temp]){ q[tail].num=temp; q[tail].step=q[head].step+1; book[temp]=1; tail++; } } for(i=0;i<10;i++){ int temp=change(t,2,i); if(!book[temp]&&z[temp]){ book[temp]=1; q[tail].num=temp; q[tail].step=q[head].step+1; tail++; } } for(i=0;i<10;i++){ int temp=change(t,3,i); if(!book[temp]&&z[temp]){ book[temp]=1; q[tail].num=temp; q[tail].step=q[head].step+1; tail++; } } for(i=1;i<10;i++){ int temp=change(t,4,i); if(!book[temp]&&z[temp]){ book[temp]=1; q[tail].num=temp; q[tail].step=q[head].step+1; tail++; } } head++; } }
