题目连接：http://poj.org/problem?id=3126 枚举每一位，看是不是素数，我的判断方法是打表判断，然后把符合条件的新数加入到队列中以便下次搜索，简单的广搜题，就是我捉急的犯了一个低级错误。   view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 #include <queue>
8 using namespace std;
9 int map[10010], n, k, f, g, h, b, a[10010];
10 queue<int> Q;
11 void prime(){
12 memset(a, -1, sizeof(a));
13 a[0] = a[1] = 0;
14 for (int i = 2; i <= 100; i++)
15 for (int j = i * i; j <= 10000; j += i)
16 a[j] = 0;
17 }
18 int fun(int a, int b, int c, int d){
19 return a * 1000 + b * 100 + c * 10 + d;
20 }
21 void init(int n){
22 f = n % 10;
23 g = n / 10 % 10;
24 h = n / 100 % 10;
25 b = n / 1000;
26 }
27 void bfs(){
28 map[n] = 0;
29 Q.push(n);
30 while (!Q.empty()){
31 int x = Q.front();
32 init(x);
33 Q.pop();
34 for (int i = 1; i < 10; i += 2){
35 int xx = fun(b, h, g, i);
36 if (a[xx] == 0) continue;
37 if (map[xx] == -1 || map[x] + 1 < map[xx]){
38 map[xx] = map[x] + 1;
39 Q.push(xx);
40 }
41 }
42 for (int i = 0; i < 10; i += 1){
43 int xx = fun(b, h, i, f);
44 if (a[xx] == 0) continue;
45 if (map[xx] == -1 || map[x] + 1 < map[xx]){
46 map[xx] = map[x] + 1;
47 Q.push(xx);
48 }
49 }
50 for (int i = 0; i < 10; i += 1){
51 int xx = fun(b, i, g, f);
52 if (a[xx] == 0) continue;
53 if (map[xx] == -1 || map[x] + 1 < map[xx]){
54 map[xx] = map[x] + 1;
55 Q.push(xx);
56 }
57 }
58 for (int i = 1; i < 10; i += 1){
59 int xx = fun(i, h, g, f);
60 if (a[xx] == 0) continue;
61 if (map[xx] == -1 || map[x] + 1 < map[xx]){
62 map[xx] = map[x] + 1;
63 Q.push(xx);
64 }
65 }
66 }
67 }
68 int main(){
69 int t;
70 prime();
71 while (~scanf("%d", &t)){
72 while (t--){
73 scanf("%d%d", &n, &k);
74 memset(map, -1, sizeof(map));
75 bfs();
76 printf("%d\n", map[k]);
77 }
78 }
79 return 0;
80 }
81
|