Prime Path

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 struct node
 7 {
 8     int k,step;
 9 };
10 
11 node h[100000];
12 bool p[11000];
13 int x,y,tot,s[11000];
14 
15 void make(int n)
16 {
17     memset(p,0,sizeof(p));
18     p[0]=1;
19     p[1]=1;
20     for(int i=2; i<=n; i++) if(!p[i])
21             for(int j=i*i; j<=n; j+=i) p[j]=1;
22 }
23 
24 int change(int x,int i,int j)
25 {
26     if(i==1) return (x/10)*10+j;else
27     if(i==2) return (x/100)*100+x%10+j*10;else
28     if(i==3) return (x/1000)*1000+x%100+j*100;else
29     if(i==4) return (x%1000)+j*1000;
30 }
31 
32 int main()
33 {
34     make(9999);
35     cin>>tot;
36     while(tot--)
37     {
38         cin>>x>>y;
39         h[1].k=x;
40         h[1].step=0;
41         int l=1,r=1;
42         memset(s,100,sizeof(s));
43         int ans=-1;
44         while(1)
45         {
46             if(h[l].k==y)
47             {
48                 ans=h[l].step;
49                 break;
50             }
51             int tk,ts;
52             for(int i=1; i<=4; i++)
53             {
54                 for(int j=0; j<=9; j++)
55                 {
56                     if(!((j==0)&&(i==4)))
57                     {
58                         tk=change(h[l].k,i,j);
59                         if(p[tk]) continue;
60                         ts=h[l].step+1;
61                         if(ts>=s[tk]) continue;
62                         if(tk==y)
63                         {
64                             ans=ts;
65                             break;
66                         }
67                         s[tk]=ts;
68                         r++;
69                         h[r].k=tk;
70                         h[r].step=ts;
71                     }
72                 }
73 
74             }
75             if(l==r||ans>=0) break;
76             l++;
77 
78         }
79         if(ans>=0) cout<<ans<<endl;
80         else cout<<" Impossible"<<endl;
81 
82     }
83     return 0;
84 }
View Code