poj3126 搜索

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <string.h>
 5 #include <math.h>
 6 #include <queue>
 7 #define MAXN 10000
 8 using namespace std;
 9 
10 int first,last;
11 int prime[MAXN];
12 void dabiao()
13 {
14     int i,j;
15     for(i = 1000;i<MAXN;i++)
16     {
17         int flag = 0;
18         for(j = 2;j<=pow(i,0.5);j++)
19         {
20             if(i%j==0)
21             {
22                 flag = 1;
23                 break;
24             }
25         }
26         if(!flag)
27             prime[i] = 1;
28     }
29 }
30 int bfs()
31 {
32     int t[4],dis[MAXN],vis[MAXN];
33     int i,j,v;
34     queue<int> q;
35     memset(dis,0,sizeof(dis));
36     memset(vis,0,sizeof(vis));
37     q.push(first);
38     vis[first] = 1;
39     while(!q.empty())
40     {
41         int x = q.front();
42         q.pop();
43         t[0] = x/1000;
44         t[1] = x%1000/100;
45         t[2] = x%100/10;
46         t[3] = x%10;
47         if(x == last)
48             return dis[x];
49         for(i = 0;i<4;i++)
50         {
51             int temp = t[i];
52             for(j = 0;j<10;j++)
53             {
54                 if(temp != j)
55                 {
56                     t[i] = j;
57                     v = t[0]*1000+t[1]*100+t[2]*10+t[3];
58                     if(!vis[v]&&prime[v])
59                     {
60                         vis[v] = 1;
61                         dis[v] = dis[x]+1;
62                         q.push(v);
63                     }
64                     if(v == last)
65                         return dis[v];
66                 }
67                 t[i] = temp;
68             }
69         }
70     }
71     return -1;
72 }
73 
74 int main()
75 {
76     //freopen("caicai.txt","r",stdin);
77     int n;
78     scanf("%d",&n);
79     dabiao();
80     while(n--)
81     {
82         cin>>first>>last;
83         int num = bfs();
84         if(num == -1)
85             cout<<"Impossible
";
86         else cout<<num<<endl;
87     }
88     return 0;
89 }