感觉似乎是水过去了？还是说这道题太水了，写完没调试测试样例正确，提交一遍过= =
思路：先素数打表，然后在进行BFS搜索，每次改变一个数字，是素数的话就加入队列中去，直到搜到最后；
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<queue> #include<vector> #define INF 1<<30 #define N 10009 using namespace std; int a[N],b[N]; queue<int>q; int n,m; int bfs() { int d[4]= {1,10,100,1000}; int k,h,tn,th,i; while(!q.empty()) q.pop(); q.push(n); b[n]=0; while(!q.empty()) { h=q.front(); q.pop(); for(i=0; i<4; i++) { for(k=0; k<=9; k++) { if(i==3&&k==0)//最高位不能为0，虽说写的是BFS，不过觉得有点像爆搜； continue; tn=h/d[i]%10; th=h-tn*d[i]+k*d[i]; if(a[th]&&b[th]==INF) { q.push(th); b[th]=b[h]+1; } if(th==m) return b[m]; } } } } int main() { int t,i,j; for(i=1; i<N; i++)//素数打表； a[i]=1; a[0]=a[1]=0; int k=sqrt(N); for(i=1; i<=k; i++) if(a[i]) for(j=i*2; j<N; j+=i) a[j]=0; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); fill(b,b+N,INF); int bb=bfs(); printf("%d\n",bb); } return 0; }
