POJ 3126

POJ3126(http://acm.pku.edu.cn/JudgeOnline/problem?id=3126)是一道很经典的广搜题。我在网上看到有多种不同的搜索思路,所以自己也把这些不同的方法一一试了遍。
方法1:从队列中取出的节点数据,分个十百千四种情况,利用i循环,推出下一节点,再使其入队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:这个方法比较巧妙,利用一个num[4]数组,可以使方法1的四种情况用一段code来解决。另外方法1和方法2都是需要判断这个数是不是素数的那种方法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:先打一个1000-10000的素数表,然后对素数表一遍一遍的搜索,每一遍都把与上个节点只差一位的数enqueue,当然,这个数据是没有被搜索过的。这个方法直接先把素数求出来,以后直接调用即可,不像前两种方法,要每一次都得判断是不是素数,应该是要快一些的,可是我测试了只有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

posted on 2009-06-05 09:22 Johnnx 阅读(1044) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

常用链接

留言簿(1)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜