Prime Path(广搜）

给定两个四位素数n,m。
每次能改变n中的一个数字，每次改变后的N也必须是素数。(首位不能改成0)
求最少经过多少次改变能使n变成m，如果无法变成则输出-1。

Input

一行，两个整数n,m。

Output

一行，最少次数或-1。

Samples

Input Copy

1033 8179

Output

6

Hint

【样例说明】
1033->1733->3733->3739->3779->8779->8179
子任务序号 子任务个数 分值 数据范围
1 3 30 不存在-1且步数小于等于5步
2 7 70 存在-1且步数大于5步

这个题就是个广搜：

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring> 
using namespace std;
const int maxn=1e5+100;
struct node{
    int w[5];
    int t;
};
int n,m; 
int cnt1,cnt;
int vis[maxn];
int biaoji[maxn];
int prime[maxn];
int p[maxn];
void inint(){
    for(int i=2;i<maxn;i++){
        if(!biaoji[i]) prime[++cnt1]=i;
        for(int j=1;j<=cnt1&&i*prime[j]<maxn;j++){
            biaoji[i*prime[j]]=1;
            if(i%prime[j]==0){
                break;
            }
        } 
    }    
    for(int i=1;i<=cnt1;i++){
        if(prime[i]>=1000&&prime[i]<=9999){
            p[++cnt]=prime[i];
        }
    }
} 
queue<node>q;
int bfs(){
    node no,ne;
    no.w[0]=n%10;
    no.w[1]=n/10%10;
    no.w[2]=n/100%10;
    no.w[3]=n/1000;
    no.t=0;
    q.push(no);
    while(!q.empty()){
        no=q.front();
        q.pop();
        for(int i=1;i<=cnt;i++){
            if(!vis[i]){
                int z=0;
                if(no.w[0]==p[i]%10){
                    z++;
                }
                if(no.w[1]==p[i]/10%10){
                    z++;
                }
                if(no.w[2]==p[i]/100%10){
                    z++;
                }
                if(no.w[3]==p[i]/1000) z++;
                if(z==3){
                    ne.w[0]=p[i]%10;
                     ne.w[1]=p[i]/10%10;
                     ne.w[2]=p[i]/100%10;
                     ne.w[3]=p[i]/1000;
                     ne.t=no.t+1;
                     if(p[i]==m){
                         return ne.t;
                    }
                    q.push(ne);
                    vis[i]=1;
                }
            }
        }
    } 
    return -1;
} 
int main(){
    inint();
    memset(vis,0,sizeof(vis));
    cin>>n>>m;
    if(n==m){
        cout<<0<<endl;
        return 0;
    } 
    int p=bfs();
    cout<<p<<endl;
}