就因為在判斷素數的時候少個等於號 糾結一天，。。。。
#include#include #include #include #include #include using namespace std; queue q; int v[10005],c; int yy[10005]; int qq(int g) { for(int i=2;i*i<=g;i++) { if(g%i==0) return 0; } return 1; } int show(int r) { int n,t; int s=0; v[r]=1; while(!q.empty()) { s++; int y=q.size(); while(y--) { int m=q.front(); q.pop(); n=m/10; for(int i=0;i<=9;i++) { t=n*10+i; if(yy[t]) {if(v[t]==1) continue; else { if(t==c) return s; else q.push(t); } v[t]=1; } } n=m/100; for(int i=0;i<=9;i++) { t=n*100+i*10+m%10; if(yy[t]) {if(v[t]==1) continue; else { if(t==c) return s; else q.push(t); } v[t]=1; } } n=m/1000; for(int i=0;i<=9;i++) { t=n*1000+i*100+m%100; if(yy[t]) {if(v[t]==1) continue; else { if(t==c) return s; else q.push(t); } v[t]=1; } } n=m%1000; for(int i=1;i<=9;i++) { t=n+i*1000; if(yy[t]) {if(v[t]==1) continue; else { if(t==c) return s; else q.push(t); } v[t]=1; } } } } return -1; } int main() { int a,b,d,i; scanf("%d",&a); memset(yy,0,sizeof(yy)); for(i=1000;i<=9999;i++) if(qq(i)) yy[i]=1; while(a--) { memset(v,0,sizeof(v)); scanf("%d %d",&b,&c); if(b==c) { printf("0\n");continue; } q.push(b); d=show(b); if(d==-1) printf("Impossible\n"); else printf("%d\n",d); while(!q.empty()) q.pop(); } return 0; }
