题目链接：传送门
题意：
给定两个四位数a，，b,每次可以改变a的任意一位，并且确保改变后的a是一个素数。
问最少经过多少次改变a可以变成b.
分析：
BFS,每次枚举改变的数，有一个剪枝，就是如果这个改变的数之前已经得到过了，
就没有必要继续变回它了。
代码如下：
#include <iostream>#include <cstring>#include <algorithm>#include <cstdio>#include <queue>using namespace std;struct nod{int a,b,c,d;int step;nod(){}nod(int _a,int _b,int _c,int _d):a(_a),b(_b),c(_c),d(_d){}};int l,r;int vis[10010];bool check(int x){for(int i=2;i*i<=x;i++)if(x%i==0) return false;return true;}bool isequal(nod tmp1,nod tmp2){if(tmp1.a==tmp2.a&&tmp1.b==tmp2.b&&tmp1.c==tmp2.c&&tmp1.d==tmp2.d)return true;return false;}void bfs(){queue<nod> Q;nod tmp,ans;tmp.a=l%10,l/=10;tmp.b=l%10,l/=10;tmp.c=l%10,l/=10;tmp.d=l%10;tmp.step=0;ans.a=r%10,r/=10;ans.b=r%10,r/=10;ans.c=r%10,r/=10;ans.d=r%10;Q.push(tmp);while(!Q.empty()){nod top = Q.front();Q.pop();if(isequal(top,ans)){printf("%d\n",top.step);return ;}for(int i=1;i<=9;i+=2){if(i!=top.a){tmp=nod(i,top.b,top.c,top.d);tmp.step=top.step+1;if(check(i+top.b*10+top.c*100+top.d*1000)&&!vis[i+top.b*10+top.c*100+top.d*1000]){Q.push(tmp);vis[i+top.b*10+top.c*100+top.d*1000]=1;}}}for(int i=0;i<=9;i++){if(i!=top.b){tmp=nod(top.a,i,top.c,top.d);tmp.step=top.step+1;if(check(i*10+top.a+top.c*100+top.d*1000)&&!vis[i*10+top.a+top.c*100+top.d*1000]){Q.push(tmp);vis[i*10+top.a+top.c*100+top.d*1000];}}}for(int i=0;i<=9;i++){if(i!=top.c){tmp=nod(top.a,top.b,i,top.d);tmp.step=top.step+1;if(check(i*100+top.b*10+top.a+top.d*1000)&&!vis[i*100+top.b*10+top.a+top.d*1000]){Q.push(tmp);vis[i*100+top.b*10+top.a+top.d*1000]=1;}}}for(int i=1;i<=9;i++){if(i!=top.d){tmp=nod(top.a,top.b,top.c,i);tmp.step=top.step+1;if(check(top.a+top.b*10+top.c*100+i*1000)&&!vis[top.a+top.b*10+top.c*100+i*1000]){Q.push(tmp);vis[top.a+top.b*10+top.c*100+i*1000]=1;}}}}puts("Impossible");return;}int main(){int n;scanf("%d",&n);while(n–){scanf("%d%d",&l,&r);memset(vis,0,sizeof(vis));bfs();}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
你可以选择这样的“三心二意”：信心恒心决心;创意乐意。
