POJ3126BFS,埃式筛选及黑科技

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 #define N 100005
7
8 bool prime[N],mark[N];
9 int in,out;
10
11 void bfs()
12 {
13 int i,j;
14 queue<int> q;
15 queue<int> a;//存步数
16
17 memset(mark,0,sizeof(mark));
18 q.push(in);
19 a.push(0);
20 mark[in]&＃61;1;
21 while (!q.empty())
22 {
23 int temp&＃61;q.front();
24 int ta&＃61;a.front();
25 q.pop();
26 a.pop();
27 if (temp&＃61;&＃61;out)
28 {
29 printf("%d\n",ta);
30 return;//出口记得return!!!
31 }
32 for (i&＃61;0;i<4;i&＃43;&＃43;)
33 {
34 for (j&＃61;0;j<&＃61;9;j&＃43;&＃43;)
35 {
36 if (0&＃61;&＃61;i&&0&＃61;&＃61;j)//是千位不能为0,所以是0&＃61;&＃61;i&&0&＃61;&＃61;j!!!
37 {
38 continue;
39 }
40 char s[6]&＃61;"\0";
41 sprintf(s,"%d",temp);
42 s[i]&＃61;j&＃43;&＃39;0&＃39;;
43 int temp1;
44 sscanf(s,"%d",&temp1);//新数要新的变量存储&＃xff0c;不能用temp!!!
45 if (prime[temp1]&&!mark[temp1])
46 {
47 q.push(temp1);
48 mark[temp1]&＃61;1;
49 a.push(ta&＃43;1);
50 }
51 }
52 }
53 }
54 printf("Impossible\n");
55 }
56
57 void cprime()//打素数表
58 {
59 int i,j;
60 memset(prime,true,sizeof(prime));
61 prime[0]&＃61;prime[1]&＃61;false;
62 for (i&＃61;2;i)
63 {
64 if (prime[i])
65 for (j&＃61;2*i;ji)
66 {
67 prime[j]&＃61;false;
68 }
69 }
70 }
71
72 int main()
73 {
74 int t;
75
76 cprime();
77 scanf("%d",&t);
78 while (t--)
79 {
80 scanf("%d %d",&in,&out);
81 bfs();
82 }
83
84 return 0;
85 }