简单题确实刷起来就是爽啊,原始的bfs,首先打一张素数表,然后根据表来进行素数的判断,可以省很多时间。
#include<cstdio> #include<cstring> #include<iostream> #include<queue> using namespace std; const int N = 10000; int ans; int pri[N]; int e1,e2,e3,e4,a,b; bool vis[N]; typedef struct { int cou,a1,a2,a3,a4; }Node; void ini() { for(int i=1;i<N;++i) pri[i] = 1; for(int i=2;i<=100;++i) { if(pri[i]==1) { for(int e=2*i;e<N;e+=i) pri[e]=0; } } } void bfs() { Node now,next; now.cou = 0; now.a1 = a/1000; now.a4 = a%10; now.a3 = (a%100)/10; now.a2 = (a/100)%10; queue<Node> q; q.push(now); memset(vis,true,sizeof(vis)); while(!q.empty()) { next = q.front(); q.pop(); if(next.a1==e1&&next.a2==e2&&next.a3==e3&&next.a4==e4) { ans = next.cou; return; } for(int i=1;i<10;++i) if(i!=next.a1) { int sum = i*1000+next.a2*100+next.a3*10+next.a4; if(pri[sum]&&vis[sum]) { vis[sum]=false; now.cou = next.cou+1; now.a1 = i; now.a2 = next.a2; now.a3 = next.a3; now.a4 = next.a4; q.push(now); } } for(int i=0;i<10;++i) { int sum = next.a1*1000+i*100+next.a3*10+next.a4; if(pri[sum]&&vis[sum]) { vis[sum]=false; now.cou = next.cou+1; now.a1 = next.a1; now.a2 = i; now.a3 = next.a3; now.a4 = next.a4; q.push(now); } } for(int i=0;i<10;++i) { int sum = next.a1*1000+next.a2*100+i*10+next.a4; if(pri[sum]&&vis[sum]) { vis[sum]=false; now.cou = next.cou+1; now.a1 = next.a1; now.a2 = next.a2; now.a3 = i; now.a4 = next.a4; q.push(now); } } for(int i=0;i<10;++i) { int sum = next.a1*1000+next.a2*100+next.a3*10+i; if(pri[sum]&&vis[sum]) { vis[sum]=false; now.cou = next.cou+1; now.a1 = next.a1; now.a2 = next.a2; now.a3 = next.a3; now.a4 = i; q.push(now); } } } } int main(void) { ini(); int ncase; cin>>ncase; while(ncase--) { scanf("%d %d",&a,&b); ans = -1; e1 = b/1000; e4 = b%10; e3 = (b%100)/10; e2 = (b/100)%10; bfs(); if(ans == -1) printf("Impossible\n"); else cout<<ans<<endl; } return 0; }