题目地址： 

题目大意： 每次只允许变动一位 求最少变动多少次可以把一个四位素数变为另一个四位素数。

还是直接bfs求最短路，每个素数是一个节点，判断是否相邻用枚举的方法，分别枚举个十百千位。 记得layer[next] = layer[cur]+1; 所以取出每一位的时候要用cur的副本

代码:

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int vis[10000];int p[10000];int layer[10000];void pre(){    p[0]=1;    p[1]=1;        for(int i=2;i<10000;i++)        if(p[i]==0)            for(int j=i*i;j<10000;j+=i)            {                p[j]=1;            }        }void init(){     memset(vis,0,sizeof(vis));     memset(layer,0,sizeof(layer));}int a,b;int bfs(){    queue
        
          q;    q.push(a);    vis[a]=1;    layer[a]=0;    while(!q.empty())    {        int cur=q.front();        int cur_cpy=cur;                q.pop();        int t[4];        for(int i=3;i>=0;i--)        {            t[i]=cur_cpy%10;            cur_cpy/=10;        }         // 枚举个位             for(int i=0;i<=9;i++)        {            int next=i;            next+=t[0]*1000+t[1]*100+t[2]*10;            if(p[next]==0&&vis[next]==0)            {                q.push(next);                vis[next]=1;                layer[next]=layer[cur]+1;                if(next==b)    return layer[next];            }                    }                // 枚举十位        for(int i=0;i<=9;i++)        {            int next=i*10;            next+=t[0]*1000+t[1]*100+t[3];            if(p[next]==0&&vis[next]==0)            {                q.push(next);                vis[next]=1;                layer[next]=layer[cur]+1;                if(next==b)    return layer[next];            }                    }                // 枚举百位                for(int i=0;i<=9;i++)        {            int next=i*100;            next+=t[0]*1000+t[2]*10+t[3];            if(p[next]==0&&vis[next]==0)            {                q.push(next);                vis[next]=1;                layer[next]=layer[cur]+1;                if(next==b)    return layer[next];            }                    }        // 枚举千位        for(int i=1;i<=9;i++)        {            int next=i*1000;            next+=t[1]*100+t[2]*10+t[3];            if(p[next]==0&&vis[next]==0)            {                q.push(next);                vis[next]=1;                layer[next]=layer[cur]+1;                if(next==b)    return layer[next];                            }                    }    }        return -1;}int main(){    pre();    int n;    cin>>n;        for(int l=0;l
         
          >a>>b; if(a==b) cout<<0<