poj 3126 素数路径

2024-01-08 06:38

文章标签 路径 poj 素数 3126

本文主要是介绍poj 3126 素数路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你2个素数，你一次只能改变素数的一位的数字（共有4位，是4位数），并且改变成的数也是素数，问你最少通过几次改变，让第1个素数等于第2个素数。

思路：用bfs，首先把给定的素数进入队列，然后穷举每位的变化，如果是素数加入队列，以此类推，到最后如果队列是空的话，就说明无解。

#include<stdio.h>
#include<string.h>
#include<math.h>
typedef struct           //C语言实现队列
{
int x;
int length;
}Box;
typedef struct
{
Box data[9001];
int front,rear;
}QuType;
#define N 10000
int vis[10000];
int prime[1229];
int a,Aim;
void pri(void) //建立素数表，好快速判断是否为素数（2分法）
{
int i,j,p[10002];
for(i=1;i<=N;i++)
  p[i]=1;
for(i=2;i*i<=N;i++)
{
  if(p[i])
  {
   for(j=i*i;j<=N;j+=i)
    p[j]=0;
  }
}
j=0;
for(i=2;i<=N;i++)
{
  if(p[i])
  {
   prime[j++]=i;
  }
}
}
int findP(int x) //2分法
{
int from=0,to=1228,mid;
    while((to-from)>=0)
{
  mid=(from+to)/2;
     if(x==prime[mid])
   return 1;
  else
   if(x>prime[mid])
    from=mid+1;
   else
                to=mid-1;
}
return 0;
}

int bfs(void)
{
QuType qu;
int find=0,s,a1,i;
qu.front=qu.rear=-1;
qu.rear++;
qu.data[qu.rear].x=a;
    qu.data[qu.rear].length=0;
vis[a]=1;
while(qu.front!=qu.rear&&!find)
{

         qu.front++;
   a1=qu.data[qu.front].x;
   if(a1==Aim)
   {
    find=1;
  // printf("%d\n",qu.data[qu.front].x);
    return qu.data[qu.front].length;
   }
   for(i=0;i<10;i++)      //穷举每一位的情况
   {
    s=a1/10*10+i;
             if(findP(s)&&!vis[s]&&s!=a1)   //如果是素数，且前面没有出现过，就加入队列（如果前面出现过还加入队列的话，就重复计算，且队列可能永远不空，死循环）
    {
                 vis[s]=1;
     qu.rear++;
     qu.data[qu.rear].x=s;
     qu.data[qu.rear].length=qu.data[qu.front].length+1;
    }
   }
   for(i=0;i<10;i++)
   {
    s=a1/100*100+i*10+a1%10;
    if(findP(s)&&!vis[s]&&s!=a1)
    {
     vis[s]=1;
     qu.rear++;
     qu.data[qu.rear].x=s;
     qu.data[qu.rear].length=qu.data[qu.front].length+1;
    }
   }
   for(i=0;i<10;i++)
   {
    s=a1/1000*1000+i*100+a1%100;
    if(s!=a1&&!vis[s]&&findP(s))
    {
     vis[s]=1;
     qu.rear++;
     qu.data[qu.rear].x=s;
     qu.data[qu.rear].length=qu.data[qu.front].length+1;
    }
   }
   for(i=1;i<10;i++)
   {
    s=i*1000+a1%1000;
    if(findP(s)&&!vis[s]&&s!=a1)
    {
     vis[s]=1;
     qu.rear++;
     qu.data[qu.rear].x=s;
     qu.data[qu.rear].length=qu.data[qu.front].length+1;
    }
   }

}
printf("Impossible\n");
return 0;
}
int main(void)
{
int i,n;
scanf("%d",&n);
while(n--)
{
   memset(vis,0,sizeof(vis));
   pri();
   scanf("%d %d",&a,&Aim);
   printf("%d\n",bfs());
}
}