题意：要求每次操作改变一位数上的数字，问进行多少次操作后前一个数可以变为后一个数 思路：直接广搜，注意千位不能为０，此题目的关键在于利用while(!q.empty())来进行计数，具体看代码；
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int MAX=1e5+1; int sushu[MAX]; int vis[MAX]; struct node { int s;//符合标准的元素 int ans;//答案 }t; void biao()//素数打表 { int b,c; for(b=2;b<=10000;b++) { if(sushu[b]==0) for(c=b*b;c<=10000;c+=b) sushu[c]=1; } } void bfs(int x,int y) { int x1,y1,i,j,ans1,ans2; node start={x,0};//定义初始结构体 queue<node>q; q.push(start); vis[x]=1; while(!q.empty()) { node tmp=q.front(); q.pop(); //千位 for(i=1;i<=9;i++) { j=i*1000+tmp.s00;//对某一位进行修改，并判断 if(vis[j]==0&&sushu[j]==0) { t.s=j; vis[j]=1; t.ans=tmp.ans+1;//ｗｈｉｌｅ函数进行的次数 if(t.s==y) { printf("%d\n",t.ans); return ; } q.push(t); } } //百位 for(i=0;i<=9;i++) { j=(tmp.s/1000)*1000+tmp.s0+i*100; if(vis[j]==0&&sushu[j]==0) { t.s=j; vis[j]=1; t.ans=tmp.ans+1; if(t.s==y) { printf("%d\n",t.ans); return ; } q.push(t); } } //十位 for(i=0;i<=9;i++) { j=(tmp.s/100)*100+tmp.s+i*10; if(vis[j]==0&&sushu[j]==0) { t.s=j; vis[j]=1; t.ans=tmp.ans+1; if(t.s==y) { printf("%d\n",t.ans); return ; } q.push(t); } } //个位 for(i=0;i<=9;i++) { j=(tmp.s/10)*10+i; if(vis[j]==0&&sushu[j]==0) { t.s=j; vis[j]=1; t.ans=tmp.ans+1; if(t.s==y) { printf("%d\n",t.ans); return ; } q.push(t); } } } } int main() { int i,n,m,j,k,l,x,y; biao(); int n1; scanf("%d",&n1); for(i=1;i<=n1;i++) { scanf("%d %d",&x,&y); memset(vis,0,sizeof(vis)); if(x!=y) { bfs(x,y); } else printf("0\n"); } } //对千位的进行操作后，符合的数字存入队列，下一次运行ｗｈｉｌｅ函数时，会以这个数的千位进行操作，百位，十位，个位同理补充某位大佬的代码（思路与上面的相同，但看起来更简洁一些）
//v[]判断素数，d[]查询是否来过 void bfs(int a,int b) { int q,d[10000]={0}; queue<int>qq; qq.push(a); d[a]=1; qq.push(-1); while(!qq.empty()) { c=qq.front(); qq.pop(); if(c==-1) { t++; qq.push(-1); continue; } if(c==b) { printf("%d\n",t); return ; } for(int i=1;i<=9;i++) { q=i*1000+c00; if(d[q]==0&&v[q]==0) { qq.push(q); d[q]=1; } } for(int i=0;i<=9;i++) { q=c/1000*1000+i*100+c0; if(d[q]==0&&v[q]==0) { qq.push(q); d[q]=1; } } for(int i=0;i<=9;i++) { q=c/100*100+i*10+c; if(d[q]==0&&v[q]==0) { qq.push(q); d[q]=1; } } for(int i=0;i<=9;i++) { q=c/10*10+i; if(d[q]==0&&v[q]==0) { qq.push(q); d[q]=1; } } } }