首页 > 代码库 > POJ - 3126 Prime Path
POJ - 3126 Prime Path
BFS，最好先打个质数表。
1 #include<stdio.h> 2 #include<assert.h> 3 #include<cmath> 4 #include<string.h> 5 //#include<queue> 6 const int maxn=15000+5; 7 int s[10]; 8 int vis[maxn],isp[maxn]; 9 using namespace std; 10 struct node{ 11 int num; 12 int cost; 13 void init(int x,int y){ 14 num=x; 15 cost=y; 16 } 17 }queue[maxn]; 18 int is_prime(int x) 19 { 20 int k=sqrt(x); 21 k=floor(k)+1; 22 assert(x>0); 23 if(x<=2) 24 return 1; 25 for(int i=2;i<=k;i++) 26 if(x%i==0) 27 return 0; 28 return 1; 29 } 30 int bfs(node source,node target) 31 { 32 int tail,head; 33 source.cost=0; 34 queue[tail=head=0].num=source.num; 35 queue[tail++].cost=0; 36 // queue<node>q; 37 // q.push(source); 38 memset(vis,0,sizeof(vis)); 39 vis[source.num]=1; 40 if(source.num==target.num) 41 return 0; 42 while(head<tail){ 43 // node a=q.front(); 44 // q.pop(); 45 node a=queue[head]; 46 int temp,midvar=a.num,cot=3; 47 while(midvar){ 48 s[cot--]=midvar%10; 49 midvar/=10; 50 } 51 // sprintf(s,"%d",a.num); 52 // int len=strlen(s); 53 for(int i=0;i<4;i++){ 54 int bufvar=s[i]; 55 for(int j=0;j<10;j++){ 56 if(i==0 && j!=0 && s[i]!=j){ 57 s[i]=j; 58 temp=s[0]*1000+s[1]*100+s[2]*10+s[3]; 59 // sscanf(s,"%d",&temp); 60 // printf("%d\n",temp); 61 if(temp==target.num) 62 return a.cost+1; 63 if(isp[temp] && !vis[temp]){ 64 // c.init(temp, a.cost+1); 65 // q.push(c); 66 queue[tail].num=temp; 67 queue[tail].cost=queue[head].cost+1; 68 tail++; 69 vis[temp]=1; 70 } 71 } 72 if(i!=0 && s[i]!=j){ 73 s[i]=j; 74 temp=s[0]*1000+s[1]*100+s[2]*10+s[3]; 75 // sscanf(s,"%d",&temp); 76 if(temp==target.num) 77 return a.cost+1; 78 if(isp[temp] && !vis[temp]){ 79 queue[tail].num=temp; 80 queue[tail].cost=queue[head].cost+1; 81 tail++; 82 vis[temp]=1; 83 } 84 } 85 } 86 s[i]=bufvar; 87 } 88 head++; 89 } 90 return -1; 91 } 92 int main() 93 { 94 int t; 95 scanf("%d",&t); 96 while(t--){ 97 node source,target; 98 scanf("%d%d",&source.num,&target.num); 99 memset(isp,0,sizeof(isp));100 for(int i=1001;i<10000;i++)101 if(is_prime(i))102 isp[i]=1;103 int mincost=bfs(source,target);104 printf("%d\n",mincost);105 }106 return 0;
//用STL中的队列
#include<stdio.h>#include<assert.h>#include<cmath>#include<string.h>#include<queue>const int maxn=10000+5;int s[10];int vis[maxn],isp[maxn];using namespace std;struct node{ int num; int cost; void init(int x,int y){ num=x; cost=y; }};int is_prime(int x){ int k=sqrt(x); k=floor(k)+1; assert(x>0); if(x<=2) return 1; for(int i=2;i<=k;i++) if(x%i==0) return 0; return 1;}int bfs(node source,node target){ source.cost=0; queue<node>q; q.push(source); memset(vis,0,sizeof(vis)); vis[source.num]=1; if(source.num==target.num) return 0; while(!q.empty()){ node a=q.front(); q.pop(); int temp,midvar=a.num,cot=3; while(midvar){ s[cot--]=midvar%10; midvar/=10; }// sprintf(s,"%d",a.num);// int len=strlen(s); for(int i=0;i<4;i++){ int bufvar=s[i]; for(int j=0;j<10;j++){ node c; if(i==0 && j!=0 && s[i]!=j){ s[i]=j; temp=s[0]*1000+s[1]*100+s[2]*10+s[3];// sscanf(s,"%d",&temp);// printf("%d\n",temp); if(temp==target.num) return a.cost+1; if(isp[temp] && !vis[temp]){ c.init(temp, a.cost+1); q.push(c); vis[temp]=1; } } if(i!=0 && s[i]!=j){ s[i]=j; temp=s[0]*1000+s[1]*100+s[2]*10+s[3];// sscanf(s,"%d",&temp); if(temp==target.num) return a.cost+1; if(isp[temp] && !vis[temp]){ c.init(temp, a.cost+1); q.push(c); vis[temp]=1; } } } s[i]=bufvar; } } return -1;}int main(){ int t; scanf("%d",&t); while(t--){ node source,target; scanf("%d%d",&source.num,&target.num); memset(isp,0,sizeof(isp)); for(int i=1001;i<10000;i++) if(is_prime(i)) isp[i]=1; int mincost=bfs(source,target); printf("%d\n",mincost); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。