POJ 3126：Prime Path（简单搜索BFS）

你的名字 2023-07-05 05:29 18阅读 0赞

# POJ 3126：Prime Path（简单搜索BFS） #

[题目链接][Link 1]

**题意：**  
每组给定两个四位数n，m；其中n和m都是素数；每次操作能改变某一位的数字，求最少需要多少步能是从n到m，而且每次操作后得到的数字都必须为素数

**题解：**  
很明显的BFS，但是开始由于脑袋没有想太清楚，一直没能AC  
其实只需要判断个十百千位的情况，判断得到的数是不是素数和是不是已经用过了即可

代码很简单易懂

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<sstream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    #define mod 1000
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn=1e5;
    const double eps=1e-8;
    int t;
    int n,m;
    int flag;
    bool vis[10010];             //判断素数
    int check[maxn+10];         //判断该数是不是已经用过
    //素数筛（埃氏筛）
    void init(){
        
        memset(vis,true,sizeof(vis));
        vis[1]=false;
        for(int i=2;i<=maxn;i++){
        
            for(int j=i*2;j<=maxn;j+=i){
        
                vis[j]=false;
            }
        }
        return ;
    }
    struct node{
        
        int x;
        int step;
        node(int xx,int s){
        
            x=xx;
            step=s;
        }
    };
    void bfs(int num,int step){
        
        check[num]=1;
        queue<node>q;
        q.push(node(num,step));
        while(!q.empty()){
        
            node now=q.front();
            q.pop();
            if(now.x==m){
        
                printf("%d\n",now.step);
                flag=1;
                return ;
            }
            for(int i=0;i<=9;i++){
                 //个位
                int fx=(now.x/10)*10+i;
                if(check[fx]==0&&vis[fx]==true){
        
                    q.push(node(fx,now.step+1));
                    check[fx]=1;
                }
            }
            for(int i=0;i<=9;i++){
                 //十位
                int fx=(now.x/100)*100+i*10+now.x%10;
                if(check[fx]==0&&vis[fx]==true){
        
                    q.push(node(fx,now.step+1));
                    check[fx]=1;
                }
            }
            for(int i=0;i<=9;i++){
                 //百位
                int fx=(now.x/1000)*1000+i*100+now.x%100;
                if(check[fx]==0&&vis[fx]==true){
        
                    q.push(node(fx,now.step+1));
                    check[fx]=1;
                }
            }
            for(int i=1;i<=9;i++){
                 //千位
                int fx=i*1000+now.x%1000;
                if(check[fx]==0&&vis[fx]==true){
        
                    q.push(node(fx,now.step+1));
                    check[fx]=1;
                }
            }
        }
        return ;
    }
    int main(){
        
        init();
        scanf("%d",&t);
        while(t--){
        
            flag=0;
            memset(check,0,sizeof(check));
            scanf("%d%d",&n,&m);
            bfs(n,0);
            if(flag==0){
        
                printf("Impossible\n");
            }
        }
        return 0;
    }

[Link 1]: https://vjudge.net/problem/POJ-3126