6.质数路径

原题：https://www.acwing.com/problem/content/description/4223/

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int N=10010;
int st[N];
int prime[N],cnt;
int dist[N];

void init(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]){
            st[i]=true;
            prime[cnt++]=i;
        }
        for(int j=0;i<=n/prime[j];j++)
        {
            st[prime[j]*i]=true;
            if(i%prime[j]==0) break;
        }
    }
}

bool check(int a,int b)
{
    int diff=0;
    for(int i=0;i<4;i++)
    {
        if(a%10!=b%10){
            diff++;
        }
        a/=10,b/=10;
    }
    if(diff==1) return true;
    return false;
}

bool bfs(int a,int b)
{
    queue<int> q;
    q.push(a);
    memset(st,0,sizeof st);
    memset(dist,0x3f,sizeof dist);
    dist[a]=0;
    while(q.size()){
        int t=q.front();
        //cout<<t<<endl;
        q.pop();
        if(t==b) return true;
        for(int i=0;i<cnt;i++)
        {
            if(prime[i]<1000||prime[i]>=10000) continue;
            if(st[prime[i]]) continue;
            if(!check(prime[i],t)) continue;
            if(dist[prime[i]]>dist[t]+1)
            {
                dist[prime[i]]=dist[t]+1;
                st[prime[i]]=true;
                q.push(prime[i]);
            }
        }
    }
    return false;
}

int main()
{
    init(N-1);
    int T;
    cin>>T;
    while(T--)
    {
        int a,b;
        cin>>a>>b;
        if(bfs(a,b)){
            cout<<dist[b]<<endl;
        }
        else puts("Impossible");
    }
    return 0;
}