POJ3126（http://acm.pku.edu.cn/JudgeOnline/problem?id=3126）是一道很經(jīng)典的廣搜題。我在網(wǎng)上看到有多種不同的搜索思路，所以自己也把這些不同的方法一一試了遍。
方法1：從隊(duì)列中取出的節(jié)點(diǎn)數(shù)據(jù)，分個(gè)十百千四種情況，利用i循環(huán)，推出下一節(jié)點(diǎn)，再使其入隊(duì)c
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 #include<stdlib.h>
5 int n,N,K;
6 typedef struct node{
7 int x,step;
8 }Node;
9 typedef struct queue{
10 Node a[10000];
11 int front,rear;
12 }Queue;
13 Queue Q;
14 int visit[10000];
15
16 void enqueue(Node data);
17 Node dequeue();
18 int isprime(int e);
19 int bfs();
20 int main()
21 {
22 while(scanf("%d",&n) != EOF){
23 while(n--){
24 scanf("%d%d",&N,&K);
25 if(N == K)printf("0\n");
26 else{
27 memset(visit,0,sizeof(visit));
28 int t = bfs();
29 if(t == -1)
30 printf("Impossible\n");
31 else
32 printf("%d\n",t);
33 }
34 }
35 }
36 system("pause");
37 return 0;
38 }
39
40 void enqueue(Node data)
41 {
42 Q.a[Q.rear++] = data;
43 }
44 Node dequeue()
45 {
46 return Q.a[Q.front++];
47 }
48
49 int isprime(int e)
50 {
51 if(!(e%2))return 0;
52 for(int k = 3;k <= sqrt(e);k+=2){
53 if(!(e%k))return 0;
54 }
55 return 1;
56 }
57
58 int bfs()
59 {
60 Node lx,lc;
61 Q.front = Q.rear = 0;
62 lx.x = N;
63 lx.step = 0;
64 visit[N] = 1;
65 enqueue(lx);
66 while(Q.front != Q.rear){
67 lc = dequeue();
68 int i;
69 for(i = 1;i < 10;i++){
70 lx.x = lc.x - lc.x%10 + i;
71 if(isprime(lx.x) && !visit[lx.x]){
72 lx.step = lc.step + 1;
73 if(lx.x == K)return lx.step;
74 visit[lx.x] = 1;
75 enqueue(lx);
76 }
77 }
78 for(i = 0;i < 10;i++){
79 lx.x = lc.x - lc.x%100 + i*10 + lc.x%10;
80 if(isprime(lx.x) && !visit[lx.x]){
81 lx.step = lc.step + 1;
82 if(lx.x == K)return lx.step;
83 visit[lx.x] = 1;
84 enqueue(lx);
85 }
86 }
87 for(i = 0;i < 10;i++){
88 lx.x = lc.x - lc.x%1000 + i*100 + lc.x%100;
89 if(isprime(lx.x) && !visit[lx.x]){
90 lx.step = lc.step + 1;
91 if(lx.x == K)return lx.step;
92 visit[lx.x] = 1;
93 enqueue(lx);
94 }
95 }
96 for(i = 1;i < 10;i++){
97 lx.x = lc.x - lc.x%10000 + i*1000 + lc.x%1000;
98 if(isprime(lx.x) && !visit[lx.x]){
99 lx.step = lc.step + 1;
100 if(lx.x == K)return lx.step;
101 visit[lx.x] = 1;
102 enqueue(lx);
103 }
104 }
105 }
106 return -1;
107 }
108
109
ode
方法2：這個(gè)方法比較巧妙，利用一個(gè)num[4]數(shù)組，可以使方法1的四種情況用一段code來(lái)解決。另外方法1和方法2都是需要判斷這個(gè)數(shù)是不是素?cái)?shù)的那種方法c
1 int bfs(int first,int last)
2 {
3 Queue q;
4 Node lx,lc;
5 int num[4];
6 q.front = q.rear = 0;
7 lx.x = first;
8 lx.step = 0;
9 visit[first] = 1;
10 q.a[q.rear++] = lx;
11 while(q.front != q.rear){
12 lc = q.a[q.front++];
13 for(int i = 0;i < 4;i++){
14 num[0] = lc.x%10;
15 num[1] = (lc.x%100)/10;
16 num[2] = (lc.x%1000)/100;
17 num[3] = lc.x/1000;
18 for(int j = 0;j < 10;j++){
19 num[i] = j;
20 lx.x = num[3]*1000 + num[2]*100 + num[1]*10 + num[0];
21 if(isprime(lx.x) && !visit[lx.x] && lx.x > 1000){
22 lx.step = lc.step + 1;
23 if(lx.x == last){
24 printf("%d\n",lx.step);
25 return 0;
26 }
27 visit[lx.x] = 1;
28 q.a[q.rear++] = lx;
29 }
30 }
31 }
32
33 }
34 return 1;
35
36 }
37
ode
方法3：先打一個(gè)1000-10000的素?cái)?shù)表，然后對(duì)素?cái)?shù)表一遍一遍的搜索，每一遍都把與上個(gè)節(jié)點(diǎn)只差一位的數(shù)enqueue，當(dāng)然，這個(gè)數(shù)據(jù)是沒(méi)有被搜索過(guò)的。這個(gè)方法直接先把素?cái)?shù)求出來(lái)，以后直接調(diào)用即可，不像前兩種方法，要每一次都得判斷是不是素?cái)?shù)，應(yīng)該是要快一些的，可是我測(cè)試了只有125MS，而方法2是63MS，整整減少了一半c
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 #include<stdlib.h>
5
6 typedef struct node{
7 int x,step;
8 }Node;
9 typedef struct queue{
10 Node a[10000];
11 int front,rear;
12 }Queue;
13 int visit[10000];
14 int primetable[1100];
15 int test[10000];
16 int sum;
17
18 void produce();
19 int chayiwei();
20 int bfs(int first,int last);
21 int main()
22 {
23 int n,N,K,t;
24 produce();
25 while(scanf("%d",&n) != EOF){
26
27 while(n--){
28
29 scanf("%d%d",&N,&K);
30 if(N == K)printf("0\n");
31 else{
32 memset(visit,0,sizeof(visit));
33 t = bfs(N,K);
34 if(t)
35 printf("Impossible\n");
36 }
37 }
38 }
39 system("pause");
40 return 0;
41 }
42
43 void produce()
44 {
45 memset(primetable,0,sizeof(primetable));
46 memset(test,0,sizeof(test));
47 for(int i=2;i<=100;++i)
48 {
49 if(!test[i])
50 {
51 for(int j=i*i;j<10000;j+=i)
52 test[j] = 1;
53 }
54 }
55 sum = 0;
56 for(int i=1000;i<10000;++i)
57 if(!test[i]) primetable[sum++]=i;
58 }
59
60 int chayiwei(int a,int b)
61 {
62 int flag = 0;
63 while(a){
64 if(a%10 != b%10)flag++;
65 a/=10;
66 b/=10;
67 }
68 if(flag == 1)return 1;
69 return 0;
70 }
71
72 int bfs(int first,int last)
73 {
74 Queue q;
75 Node lx,lc;
76 q.front = q.rear = 0;
77 lx.x = first;
78 lx.step = 0;
79 visit[first] = 1;
80 q.a[q.rear++] = lx;
81 while(q.front != q.rear){
82 lc = q.a[q.front++];
83 for(int i = 0;i < sum;i++){
84
85 lx.x = primetable[i];
86 if(chayiwei(lc.x,lx.x) && !visit[lx.x]){
87 lx.step = lc.step + 1;
88 if(lx.x == last){
89 printf("%d\n",lx.step);
90 return 0;
91 }
92 visit[lx.x] = 1;
93 q.a[q.rear++] = lx;
94 }
95 }
96 }
97 return 1;
98
99 }
100
ode