首页 > 代码库 > poj3126(Prime Path)
poj3126(Prime Path)
题目地址：Prime Path
题目大意：
给你两个四位数的素数，通过改变其中的一个数，每次只允许改变一位数，而且改变之后的数也必须是个素数，问你最少通过改变几次变成后一个四位的素数。如果不能改变成后面的四位素数则输出Impossible。
解题思路：
广搜，枚举改变每一位（千、百、十、个）数 进队列。素数筛选到sqrt，减少时间复杂度，vis标记，进出队列时都标记，减少时间复杂度。郁闷，在处理改变数的个十百千位的时候，忘记要处理的aaa值已经改变，以至于这个式子cnt[aa]=cnt[aaa]+1.就一直不对。浪费太多时间。
代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 #define PI 3.1415927 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {0,-1,0,1}; 26 const int d1y[]= {-1,0,1,0}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 const int dirx[]= {-1,1,-2,2,-2,2,-1,1}; 32 const int diry[]= {-2,-2,-1,-1,1,1,2,2}; 33 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 34 /***************************************/ 35 void openfile() 36 { 37 freopen("data.in","rb",stdin); 38 freopen("data.out","wb",stdout); 39 } 40 priority_queue<int> qi1; 41 priority_queue<int, vector<int>, greater<int> >qi2; 42 /**********************华丽丽的分割线,以上为模板部分*****************/ 43 const int M=10001; 44 int vis[M],cnt[M]; 45 int isprime[M]; 46 int di[10]= {0,1,2,3,4,5,6,7,8,9}; 47 int ea; 48 int ce; 49 void judgeprime() 50 { 51 int i,j; 52 isprime[0]=1; 53 isprime[1]=1; 54 for(i=2; i<sqrt(M); i++) 55 if (!isprime[i]) 56 { 57 for(j=i+i; j<M; j+=i) 58 isprime[j]=1; 59 } 60 } 61 int BFS(int a) 62 { 63 queue<int >Q; 64 int i,j,k,h; 65 int aa,ge,shi,bai,qi; 66 Q.push(a);; 67 while(!Q.empty()) 68 { 69 int aaa=Q.front(); 70 Q.pop(); 71 vis[aaa]=1; 72 if (aaa==ea) 73 { 74 ce=cnt[aaa]; 75 return 0; 76 } 77 int ce1=aaa; 78 for(i=1; i<10; i+=2) //个位 79 { 80 aaa=ce1; 81 aaa=aaa-aaa%10; 82 aa=aaa+di[i]; 83 if(!vis[aa]&&!isprime[aa]) 84 { 85 cnt[aa]=cnt[ce1]+1; 86 Q.push(aa); 87 vis[aa]=1; 88 } 89 } 90 91 for(i=0; i<10; i++) //十位 92 { 93 aaa=ce1; 94 ge=aaa%10; 95 aaa=aaa/100; 96 aa=aaa*100+di[i]*10+ge; 97 if(!vis[aa]&&!isprime[aa]) 98 { 99 cnt[aa]=cnt[ce1]+1;100 Q.push(aa);101 vis[aa]=1;102 }103 }104 105 for(i=0; i<10; i++) //百位106 {107 aaa=ce1;108 ge=aaa%10;109 aaa=aaa/10;110 shi=aaa%10;111 aaa=aaa/100;112 aa=aaa*1000+di[i]*100+shi*10+ge;113 if(!vis[aa]&&!isprime[aa])114 {115 cnt[aa]=cnt[ce1]+1;116 Q.push(aa);117 vis[aa]=1;118 }119 }120 121 for(i=1; i<10; i++) //千位122 {123 aaa=ce1;124 ge=aaa%10;125 aaa=aaa/10;126 shi=aaa%10;127 aaa=aaa/10;128 bai=aaa%10;129 aaa=aaa/100;130 aa=di[i]*1000+bai*100+shi*10+ge;131 if(!vis[aa]&&!isprime[aa])132 {133 cnt[aa]=cnt[ce1]+1;134 Q.push(aa);135 vis[aa]=1;136 }137 }138 }139 return 0;140 }141 int main()142 {143 144 int cas;145 scanf("%d",&cas);146 while(cas--)147 {148 int sa;149 memset(vis,0,sizeof(vis));150 memset(cnt,0,sizeof(cnt));151 memset(isprime,0,sizeof(isprime));152 ce=-1;153 scanf("%d%d",&sa,&ea);154 judgeprime();155 BFS(sa);156 if (ce==-1)157 printf("Impossible\n");158 else159 printf("%d\n",ce);160 }161 return 0;162 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。