首页 > 代码库 > poj 3126 Prime Path （bfs）

poj 3126 Prime Path （bfs）

2024-07-14 07:48:21   215人阅读

链接：poj 3126

题意：给定两个素数四位m,n（不含前导0）,求从m转化到n至少需要几次

转化规则：每次转化y与x只有一位数字不同，且y为素数

若能从m转化为n,输出转化的最小次数，否则输出Impossible

分析：因为要用到四位数的素数，首先用筛选法求出素数.然后分别只变换个位，十位，百位，千位四种情况来bfs

注意：最高位数字不能为0，对于四位素数肯定都是奇数，这样可以减少bfs次数

#include<cstdio>#include<cstring>#include<queue>using namespace std;int a[100010]={1,1,0},n,m,c[4];int vis[10010],dis[10010];queue<int> q;void prime()                    //筛选法求素数{    int i,j;    for(i=2;i<=10000;i++)        if(a[i]==0)            for(j=i+i;j<=10000;j+=i)                a[j]=1;}void ispush(int top,int x)      //判断是否符合条件{    if(!a[x]&&!vis[x]){        q.push(x);        vis[x]=1;        dis[x]=dis[top]+1;    }}int bfs(){    int i,t,j,top,x;    memset(vis,0,sizeof(vis));    memset(dis,0,sizeof(vis));    vis[n]=1;    while(!q.empty())        q.pop();    q.push(n);    while(!q.empty()){        top=q.front();        q.pop();        if(top==m)            return 0;        t=1;        for(i=0;i<=3;i++){           //求各位的数字            c[i]=top/t%10;            t*=10;        }        for(j=1;j<=9;j+=2){                  //变换个位，四位数的素数都是奇数            x=c[3]*1000+c[2]*100+c[1]*10+j;            ispush(top,x);        }        for(j=0;j<=9;j++){                     //变换十位            x=c[3]*1000+c[2]*100+j*10+c[0];            ispush(top,x);        }         for(j=0;j<=9;j++){                       //变换百位            x=c[3]*1000+j*100+c[1]*10+c[0];            ispush(top,x);        }        for(j=1;j<=9;j++){                    //变换千位            x=j*1000+c[2]*100+c[1]*10+c[0];            ispush(top,x);        }    }    return -1;}int main(){    int T,sum;    scanf("%d",&T);    prime();    while(T--){        scanf("%d%d",&n,&m);        sum=bfs();        if(sum==-1)            printf("Impossible\n");        else            printf("%d\n",dis[m]);    }    return 0;}
View Code

 


联系
我们