Poj 3126 Prime Path (BFS+筛素数)

accbulb / 2024-02-03 / 原文

#include<iostream>
#include<queue>
#include<cstring>
const int N=10010;
int t,aa,bb,prime[N],vis[N],step[N];
using namespace std;
void prime_(){ //埃式筛法
    prime[0]=prime[1]=1;
    for(int i=2;i<10000;i++){
        if(prime[i]) continue;
        for(int j=i*2;j<10000;j+=i){
            prime[j]=1;
        }
    }
}
void bfs(int aa,int bb){
    queue<int> q;
    int a,b,c,d,s,x;
    q.push(aa);
    while(!q.empty()){
        x=q.front();
        q.pop();
        if(x==bb){
            cout<<step[x]<<endl;
            return ;
        }
        a=x/1000; //千 
        b=(x/100)%10; //百 
        c=(x%100)/10;//十 
        d=x%10;//个 
        for(int i=1;i<=9;i++){ //枚举千位 
            if(i==a) continue;
            s=i*1000+b*100+c*10+d;
            if(prime[s]==0 && !vis[s]){
                vis[s]=1;
                step[s]=step[x]+1;
                q.push(s);
            }
        }
        for(int i=0;i<=9;i++){ //枚举百位 
            if(i==b) continue;
            s=a*1000+i*100+c*10+d;
            if(prime[s]==0 && !vis[s]){
                vis[s]=1;
                step[s]=step[x]+1;
                q.push(s);
            }
        }
        for(int i=0;i<=9;i++){ //枚举十位
            if(i==c) continue;
            s=a*1000+b*100+i*10+d;
            if(prime[s]==0 && !vis[s]){
                vis[s]=1;
                step[s]=step[x]+1;
                q.push(s);
            }
        }
        for(int i=0;i<=9;i++){ //枚举个位
            if(i==d) continue;
            s=a*1000+b*100+c*10+i;
            if(prime[s]==0 && !vis[s]){
                vis[s]=1;
                step[s]=step[x]+1;
                q.push(s);
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    prime_();
    cin>>t;
    while(t--){
        cin>>aa>>bb;
        memset(vis,0,sizeof(vis));
        memset(step,0,sizeof(step));
        bfs(aa,bb);
    }
    return 0;
}