题目地址：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 else 159 printf("%d\n",ce); 160 } 161 return 0; 162 }
poj3126(Prime Path),布布扣,bubuko.com
原文：http://www.cnblogs.com/ZhaoPengkinghold/p/3891845.html
