poj 3126 Prime Path （广搜）

用户1624346

发布于 2018-04-17 08:08:38

54500

代码可运行

文章被收录于专栏：calmoundcalmound

运行总次数：0

代码可运行

http://poj.org/problem?id=3126

题意：从一个素数，挨个数位的变换，在此过程中保证每次变换的数位都是素数，最后变到所给的另一个素数最少步多少

分析：广搜，依次换一位数字，判断该数字是否是素数，若是进队列，其中需要注意的是，换千位数字的时候可能会出现

0的情况，导致所给数字不是4位数

#include<stdio.h>
#include<queue>
#include<string.h>
#include<math.h>
using namespace std;
const int MAXN=20000;
int vis_prime[MAXN];
int vis[MAXN];
int step[MAXN];

void init()
{
    memset(vis_prime,0,sizeof(vis_prime));
    for(int i=2; i<=(int)sqrt(1.0*MAXN); i++)
    {
        if(vis_prime[i]==0)
          {
            for(int j=i*2; j<MAXN; j+=i)
            {
                vis_prime[j]=1;
            }
          }
    }
    //for(int i=1000;i<MAXN/2;i++) if(vis_prime[i]==0) printf("%d ",i);


}

int BFS(int a,int b)
{
    int head,next,i,j;
    memset(vis,0,sizeof(vis));
    queue<int>Q;
    Q.push(a);
    vis[a]=1;
    step[a]=0;
    while(!Q.empty())
    {
        head=Q.front();
        Q.pop();
        for(i=0;i<4;i++)
        {
            for(j=0;j<=9;j++)
            {
                if(i==0) next=head/10*10+j;
                if(i==1) next=head/100*100+j*10+head%10;
                if(i==2) next=head/1000*1000+head%100+j*100;
                if(i==3) next=j*1000+head%1000;
                if(next==b) return step[head]+1;
                if(!vis_prime[next] && !vis[next] && next>=1000)//这里要保证是4位数字
                {//有可能17是素数，这样很可能就减少了步数到b，而4位数字的话，可能步数就得多一点了
                    vis[next]=1;
                    Q.push(next);
                    step[next]=step[head]+1;
                }
            }
        }
    }
    return 0;
}

int main()
{
    int T,a,b;
    init();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&a,&b);
        if(a==b) printf("0\n");
        else
        {
            int ans=BFS(a,b);
            if(ans==0) printf("Impossible\n");
            else printf("%d\n",ans);
        }
    }
    return 0;
}