本文主要是介绍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());
}
}
这篇关于poj 3126 素数路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
