BFS-poj3126【Prime Path】

题意：给出起始素数和目标素数，一次可以改变一位（改变完的那个数字也必须要是素数），现在要问最少多少次可以转移到目标素数
素数筛+BFS
代码如下：

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<sstream>
#include<stack>
#include<set>
#include<bitset>
#include<vector>
#include<iomanip>
#define ll long long
#define INF 0x3f3f3f3f
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=1e4+5;
const ll mod=1e5+7;
inline int read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; } ;
const int n=10000;
int vis[maxn];
int num;
bool visprime[maxn];
int prime[maxn];

struct node{
    int x,cnt;
};

void init()
{
    for(int i=2;i<=n;i++)
    {
        if(visprime[i]==false) prime[++num]=i;
        for(int j=1;j<=num;j++)
        {
            if(i*prime[j]>n) break;
            visprime[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}

bool judge(int x,int y)
{
    int sum=0;
    int temp1,temp2;
    while(x!=0)
    {
        temp1=x%10;
        temp2=y%10;
        if(temp1!=temp2) sum++;
        x/=10;
        y/=10;
    }
    if(sum==1) return true;
    return false;
}

int bfs(int u,int v)
{
    vis[u]=1;
    node now,next;
    now.x=u,now.cnt=0;
    queue<node>q;
    q.push(now);
    while(!q.empty())
    {
        now=q.front();
        //printf("%d\n",now.x);
        q.pop();
        if(now.x==v) return now.cnt;
        for(int i=1;i<=num;i++)
        {
            if(!vis[prime[i]]&&judge(prime[i],now.x)&&prime[i]>1000&&prime[i]<10000)
            {
                vis[prime[i]]=1;
                next.x=prime[i];
                next.cnt=now.cnt+1;
                q.push(next);
            }
        }
    }
    return -1;
}

int main()
{

    init();
    int _;_=read();while(_--)
    {
        int a=read(),b=read();
        int ans=bfs(a,b);
        if(ans==-1) puts("Impossible");
        else printf("%d\n",ans);
        memset(vis,0,sizeof(vis));
    }
}