题意：给出起点素数，只能变4位上的一个数变成零一个素数，求变成终止的素数至少需要多少不？
思路：很容易想到BFS而且素数筛选，但是素数之间的关系有点不好办，起初想用map[][]来存，如果能变成另一个素数为1，然后BFS（）；必然会超时啊，然后用vectot<>去存，解雇还会超时，然后想到，不用预先存下来。在BFS的时候0~9枚举改改变四位上的数，，，果然过了。唉，本来想刷水题的，还卡了很久，，，
超时代码：
Source Code
| Problem: 3126 | User: 1013101127 | |
| Memory: N/A | Time: N/A | |
| Language: C++ | Result: Time Limit Exceeded |
- Source Code
#include <iostream> #include <set> #include <string> #include <cstdio> #include <algorithm> #include <queue> #include <cstring> using namespace std; const int MA=10000; int n; //int map[1000][1000]; int prim [MA]; bool num[10001]; int k; void PRIM() { memset(num,0,sizeof(num)); k=1; for(int i=2;i<=10000;i++) { if(num[i]==0) { if(i>1000) prim[k++]=i; for(int j=i;j<10001;j+=i) num[j]=1; } } } int relaton(int a,int b) { int flag=0; for(int i=0;i<4;i++) { int aa=a%10; int bb=b%10; if(aa==bb) flag++; a/=10; b/=10; } if(flag==3) return 1; else return 0; } /* void initmap() { for(int i=1;i<k;i++) { for(int j=1;j<k;j++) { if(relaton(prim[i],prim[j])) map[prim[i]][prim[j]]=map[prim[j]][prim[i]]=1; else map[prim[i]][prim[j]]=map[prim[j]][prim[i]]=0; } } }*/ int x,y; struct Node { int no; int sum; }; Node s,e; int BFS() { queue<Node>Q; Q.push(s); Node tmp,ne; while(!Q.empty()) { tmp=Q.front(); if(tmp.no==e.no) return tmp.sum+1; Q.pop(); for(int i=1;i<k;i++) { if(relaton(tmp.no,prim[i])) { ne.no=prim[i]; ne.sum=tmp.sum+1; Q.push(ne); } } } return -1; } int main() { PRIM(); int cas; cin>>cas; while(cas--) { cin>>x>>y; if(x==y) { cout<<'0'<<endl; continue; } s.no=x;s.sum=0; e.no=y; int ans=BFS(); if(ans==-1) cout<<"Impossible"<<endl; else cout<<ans-1<<endl; } return 0; }
AC代码：
Source Code
| Problem: 3126 | User: 1013101127 | |
| Memory: 752K | Time: 16MS | |
| Language: G++ | Result: Accepted |
- Source Code
#include<iostream> #include<cstdio> #include <cstring> #include <cmath> using namespace std; class number { public: int prime; int step; }; bool JudgePrime(int digit) { if(digit==2 || digit==3) return true; else if(digit<=1 || digit%2==0) return false; else if(digit>3) { for(int i=3;i*i<=digit;i+=2) if(digit%i==0) return false; return true; } } int a,b; bool vist[15000]; number queue[15000]; void BFS() { int i; //temporary int head,tail; queue[head=tail=0].prime=a; queue[tail++].step=0; vist[a]=true; while(head<tail) { number x=queue[head++]; if(x.prime==b) { cout<<x.step<<endl; return; } int unit=x.prime%10; //获取x的个位 int deca=(x.prime/10)%10; //获取x的十位 for(i=1;i<=9;i+=2) //枚举x的个位，保证四位数为奇数（偶数必不是素数） { int y=(x.prime/10)*10+i; if(y!=x.prime && !vist[y] && JudgePrime(y)) { vist[y]=true; queue[tail].prime=y; queue[tail++].step=x.step+1; } } for(i=0;i<=9;i++) //枚举x的十位 { int y=(x.prime/100)*100+i*10+unit; if(y!=x.prime && !vist[y] && JudgePrime(y)) { vist[y]=true; queue[tail].prime=y; queue[tail++].step=x.step+1; } } for(i=0;i<=9;i++) //枚举x的百位 { int y=(x.prime/1000)*1000+i*100+deca*10+unit; if(y!=x.prime && !vist[y] && JudgePrime(y)) { vist[y]=true; queue[tail].prime=y; queue[tail++].step=x.step+1; } } for(i=1;i<=9;i++) //枚举x的千位,保证四位数，千位最少为1 { int y=x.prime%1000+i*1000; if(y!=x.prime && !vist[y] && JudgePrime(y)) { vist[y]=true; queue[tail].prime=y; queue[tail++].step=x.step+1; } } } cout<<"Impossible"<<endl; return; } int main() { int test; cin>>test; while(test--) { cin>>a>>b; memset(vist,false,sizeof(vist)); BFS(); } return 0; }