题目链接：传送门

题意：

给定两个四位数a，b,每次可以改变a的任意一位，并且确保改变后的a是一个素数。

问最少经过多少次改变a可以变成b.

分析：

BFS,每次枚举改变的数，有一个剪枝，就是如果这个改变的数之前已经得到过了，

就没有必要继续变回它了。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        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
       
         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; } 
       
      
     
    
   
  

?

?

?

?