poj3126 Prime Path 宽搜

这题就是宽搜，枚举每个点，但是要注意num[0]（千位的位置）不能为0需要判断一下，然后再优化一下，就OK了。如果不优化的话，就会TLE。
 1 #include <stdio.h>
 2 #include <cmath>
 3 #include <iostream>
 4 #include <string.h>
 5 #include <queue>
 6 using namespace std;
 7 struct node
 8 {
 9     int num[4];
10     int step;
11 };
12 bool isPrim[10000+10];
13 bool v_num[10000+10];
14 bool judge(int n)
15 {
16     int i;
17     for(i=2;i<=sqrt(n);++i)
18     {
19         if(n%i==0)
20             return 0;
21     }
22     return 1;
23 }
24 void init()
25 {
26     int i;
27     for(i=1;i<=9999;++i)
28     {
29         if(judge(i))
30             isPrim[i]=1;
31         else
32             isPrim[i]=0;
33     }
34     return ;
35 }
36 int bfs(node begin,int aim)
37 {
38     int i,j,k;
39     int cnt=10;
40     int temp;
41     int number;
42     node t,t1,t2;
43     queue<node>haha;
44     haha.push(begin);
45     while(haha.size()>0)
46     {
47         t=haha.front();
48         haha.pop();
49         for(i=0;i<4;++i)
50         {
51             t1=t;
52             t1.step=t.step+1;
53             temp=cnt;
54             while(temp--)
55             {
56                 t1.num[i]=(t1.num[i]+1)%10;
57                 number=t1.num[0]*1000+t1.num[1]*100+t1.num[2]*10+t1.num[3];
58                 //printf("haha=%d\n",number);
59                 if(number==aim)
60                     return t1.step;
61                 if(isPrim[number]&&v_num[number]==0&&number/1000!=0)
62                 {
63                     v_num[number]=1;
64                     haha.push(t1);
65                 }
66             }
67         }
68     }
69     return -1;
70 }
71 int main()
72 {
73     init();
74     int a,b;
75     int t;
76     int res;
77     node begin;
78     scanf("%d",&t);
79     while(t--)
80     {
81         memset(v_num,0,sizeof(v_num));
82         scanf("%d%d",&a,&b);
83         if(a==b)
84         {
85             printf("0\n");
86             continue;
87         }
88         begin.num[0]=a/1000;
89         begin.num[1]=(a/100)%10;
90         begin.num[2]=(a/10)%10;
91         begin.num[3]=a%10;
92         begin.step=0;
93         //printf("begin =%d\n",begin.num[0]*1000+begin.num[1]*100+begin.num[2]*10+begin.num[3]);
94         v_num[a]=1;
95         res=bfs(begin,b);
96         printf("%d\n",res);
97     }
98     return 0;
99 }