poj3126Prime Path

给定两个四位素数a b，要求把a变换到b
变换的过程要 每次变换出来的数都是一个 四位素数，而且当前这步的变换所得的素数 与 前一步得到的素数 只能有一个位不同，而且每步得到的素数都不能重复。

///果不其然各种姿势操T了,在暴力的时候，调用了太多的C++库文件
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <queue>
using namespace std;
const int maxn=2e5;
bool a[maxn];
bool prime[maxn];
bool vis[maxn];
int step[maxn];
string n,m;
int cnt=0;//四位数的素数也就有1061个
void getprime(){
    memset(a,false,sizeof(a));
    memset(prime,false,sizeof(prime));
    for(int i=2; i<10000; ++i){
        if(!a[i]){
            if(i>=1000)
              prime[i]=true;
            for(int j=i*i; j<10000; j+=i)
                a[j]=true;
        }
    }
}
void bfs(){
    memset(vis,false,sizeof(vis));
    string tmp;
    queue<string>q;
    q.push(m);
    int mm=atoi(m.c_str());
    vis[mm]=1;
    step[mm]=0;
    int k=0;
    while(!q.empty()){
        string p=q.front();
        q.pop();
        int pp=atoi(p.c_str());
        if(p==n){
            printf("%d\n",step[pp]);
            return ;
        }
        for(int i=0; i<=9; ++i){
            for( k=0; k<4; ++k){
                tmp.clear();
                for(int j=0; j<k; ++j)   tmp+=p[j];
                stringstream ss;    ss<<i;  tmp+=ss.str();//tmp+=std::to_string(i);
                for(int j=k+1; j<4; ++j) tmp+=p[j];
                int tmpp=atoi(tmp.c_str());
                if(prime[tmpp]&&!vis[tmpp]){
                    q.push(tmp);
                    step[tmpp]=step[pp]+1;
                    vis[tmpp]=true;
                }
            }
        }
    }
    printf("Impossible\n");
}
int main(){
    getprime();
    int t;
    scanf("%d",&t);
    while(t--){
        cin>>m>>n;
        bfs();
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <queue>
using namespace std;
const int maxn=2e5;
bool a[maxn];
bool prime[maxn];
bool vis[maxn];
int step[maxn];
int n,m;
int cnt=0;//四位数的素数也就有1061个
void getprime(){
    memset(a,false,sizeof(a));
    memset(prime,false,sizeof(prime));
    for(int i=2; i<10000; ++i){
        if(!a[i]){
            if(i>=1000)
              prime[i]=true;
            for(int j=i*i; j<10000; j+=i)
                a[j]=true;
        }
    }
}
//将number的倒数第pos位置变为val
int get(int num,int pos,int val){
    switch(pos){
        case 0:return num/10*10+val;
        case 1:return num/100*100+val*10+num%10;
        case 2:return num/1000*1000+val*100+num%100;
        case 3:return val*1000+num%1000;
    }
}
void bfs(){
    memset(vis,false,sizeof(vis));
    queue<int>q;
    q.push(m);
    vis[m]=1;
    step[m]=0;
    int k=0;
    while(!q.empty()){
        int p=q.front();
        q.pop();

        if(p==n){
            printf("%d\n",step[p]);
            return ;
        }
        for(int i=0; i<=9; ++i){
            for( k=0; k<4; ++k){
               //if(k==3&&i==0) continue;
                int tmp=get(p,k,i);
                if(prime[tmp]&&!vis[tmp]){
                    q.push(tmp);
                    step[tmp]=step[p]+1;
                    vis[tmp]=true;
                }
            }
        }
    }
    printf("Impossible\n");
}
int main(){
    int t;
    getprime();
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&m,&n);
        bfs();
    }
    return 0;
}