poj 3126 Prime Path( bfs + 素数)

题意：给定两个四位数，求从前一个数变到后一个数最少需要几步，改变的原则是每次只能改变某一位上的一个数，而且每次改变得到的必须是一个素数；

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<stack>
 6 #include<queue>
 7 #include<iomanip>
 8 #include<cmath>
 9 #include<map>
10 #include<vector>
11 #include<algorithm>
12 using namespace std;
13 
14 int p[10010],vis[10010];
15 int a,b,t;
16 struct node
17 {
18     int a,step;
19 }pos,next;
20 void prime() //快速求素数的模板
21 {
22     int i,j;
23     memset(p,-1,sizeof(p));
24     p[0]=p[1]=0;
25 
26     for(i=3; i<10005; i++)
27     {
28         if(i%2==0) p[i]=0;
29         if(p[i])
30         for(j=i*2; j<10005; j+=i)
31         p[j]=0;
32     }
33 }
34 int change(int x,int i,int j) //i代表改变哪一位（个十百千），j代表改变为几，x是原数
35 {
36     if(i==1)  return (x/10)*10+j;
37     else if(i==2) return (x/100)*100+x%10+j*10;
38     else if(i==3) return (x/1000)*1000+x%100+j*100;
39     else if(i==4) return (x%1000)+j*1000;
40     return 0;
41 }
42 void bfs()
43 {
44     int i,j;
45     queue<node>q;
46     next.a=a; next.step=0;
47     vis[a]=1;
48     q.push(next);
49     while(!q.empty())
50     {
51         pos=q.front();
52         q.pop();
53         next.step=pos.step+1;
54         for(i=1; i<=4; i++)
55         for(j=0; j<10; j++)
56         {
57             if(i==4&&j==0)
58             continue;
59             next.a=change(pos.a,i,j);
60             if(next.a==b)
61             {
62                 cout<<next.step<<endl;
63                 return;
64             }
65             if(p[next.a]&&!vis[next.a])
66             {
67                 q.push(next); vis[next.a]=1;
68             }
69         }
70     }
71     cout<<"Impossible"<<endl;
72 }
73 int main()
74 {
75     prime();
76     cin>>t;
77     while(t--)
78     {
79         memset(vis,0,sizeof(vis));
80         cin>>a>>b;
81         if(a==b)
82         {
83             cout<<"0"<<endl;
84             continue;
85         }
86         bfs();
87     }
88     return 0;
89 }