POJ-3126 Prime Path---BFS+素数打表

题目链接：

题目大意：

给两个四位数a,b 每次改变a中的一位而且改动之后的必须是素数，问最少改动几次可以到b?(永远达不到b就输出impossible)

思路：

素数打表更好直接判断，然后BFS，用力一点小技巧可以直接生成所有可到达的点

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<cstdio>
 7 #include<set>
 8 #include<map>
 9 #include<cmath>
10 using namespace std;
11 typedef pair<int, int> Pair;
12 typedef long long ll;
13 const int INF = 0x3f3f3f3f;
14 int T, n, m;
15 const int maxn = 10000 + 10;
16 bool is_prime[maxn];
17 void init()
18 {
19     for(int i = 2; i < maxn; i++)is_prime[i] = 1;
20     for(int i = 2; i * i < maxn; i++)
21     {
22         if(is_prime[i])
23         {
24             for(int j = i * i; j < maxn; j += i)is_prime[j] = 0;
25         }
26     }
27     //for(int i = 0; i < maxn; i++)if(is_prime[i])cout<<i<<endl;
28 }
29 bool v[maxn];
30 void bfs()
31 {
32     int a[4], b[4];
33     b[0] = 1000, b[1] = 100, b[2] = 10, b[3] = 1;
34     queue<Pair>q;
35     memset(v, 0, sizeof(v));
36     q.push(Pair(n, 0));
37     v[n] = 1;
38 
39     while(!q.empty())
40     {
41         Pair now = q.front();
42         q.pop();
43         int x = now.first;
44         if(x == m)
45         {
46             cout<<now.second<<endl;
47             return;
48         }
49         a[0] = x % 1000;//每一位置为0
50         a[1] = x - x / 100 % 10 * 100;
51         a[2] = x - x / 10 % 10 * 10;
52         a[3] = x - x % 10;
53         for(int i = 0; i < 4; i++)//生成所有的可变化的四位数
54         {
55             for(int j = 0; j < 10; j++)
56             {
57                 int y = a[i] + j * b[i];
58                 if(y < 1000 || y == x || !is_prime[y] || v[y])continue;
59                 v[y] = 1;
60                 q.push(Pair(y, now.second + 1));
61             }
62         }
63     }
64     cout<<"Impossible"<<endl;
65     return;
66 }
67 int main()
68 {
69     init();
70     cin >> T;
71     while(T--)
72     {
73         cin >> n >> m;
74         bfs();
75     }
76 }