問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3126思路:
BFS，一次AC
代碼:
1 #define QUEUE_LEN 10000
2 int from, to;
3 int head, tail;
4 struct EACH {
5 int plen;
6 int num;
7 } queue[QUEUE_LEN];
8 int hash[QUEUE_LEN];
9
10 int
11 is_prime(int num)
12 {
13 int i, up = (int)sqrt(num*1.0);
14 for(i=2; i<=up; i++)
15 if(num%i == 0)
16 return 0;
17 return 1;
18 }
19
20 int
21 bfs()
22 {
23 int cur_plen, cur_num, next_num;
24 int i, j, k, t, div;
25 queue[tail].plen = 0;
26 queue[tail].num = from;
27 hash[queue[tail].num] = 1;
28 while(head < tail) {
29 ++head;
30 cur_plen = queue[head].plen;
31 cur_num = queue[head].num;
32 if(cur_num == to)
33 return cur_plen;
34 div = 1000;
35 t = cur_num;
36 for(i=3; i>=0; i--) {
37 k = t/div;
38 for(j=0; j<=9; j++) {
39 if(i==3 && j==0)
40 continue;
41 next_num = cur_num;
42 next_num -= k*div;
43 next_num += j*div;
44 if(!hash[next_num] && is_prime(next_num)) {
45 ++tail;
46 queue[tail].plen = cur_plen + 1;
47 queue[tail].num = next_num;
48 hash[queue[tail].num] = 1;
49 }
50 }
51 t = t%div;
52 div /= 10;
53 }
54 }
55 return -1;
56 }