Prime Path
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1877 Accepted: 1215

Description

The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.

Now, the minister of finance, who had been eavesdropping, intervened.
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
— Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you?
— In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.
1033
1733
3733
3739
3779
8779
8179
The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

Input

One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).

Output

One line for each case, either with a number stating the minimal cost or containing the word Impossible.

Sample Input

```3
1033 8179
1373 8017
1033 1033```

Sample Output

```6
7
0```

Source Code

 Problem: 3126 User: luoguangyao Memory: 344K Time: 47MS Language: C++ Result: Accepted
• Source Code
•   1#include <iostream>
2#include <math.h>
3#include <queue>
4#include <stdio.h>
5
6using namespace::std;
7
8int cnumber[10000];
9
10bool mark[10000];
11
12
13bool isprimer(int npp)
14{
15    for (int q = 2; q <= sqrt(double(npp)); ++q)
16    {
17        if (npp % q == 0)
18        {
19            return 0;
20        }

21    }

22    return 1;
23
24}

25
26
27int main()
28{
29
30//    freopen("1.txt","r",stdin);
31
32    int n;
33    cin >> n;
34
35    while (n)
36    {
37        queue<int> number;
38        int x;
39        int y;
40        int i;
41        int j;
42        int newnumber;
43
44        memset(cnumber,0,sizeof(cnumber));
45        memset(mark,0,sizeof(mark));
46
47        cin >> x >> y;
48
49
50        cnumber[x] = 0;
51
52        number.push(x);
53
54        while (number.size())
55        {
56            newnumber = number.front();
57
58            int p = (newnumber % 1000/ 100;
59
60            int p1 = newnumber % 1000 % 100 / 10;
61
62            number.pop();
63
64            mark[newnumber] = 1;
65
66            if (newnumber == y)
67            {
68                break;
69            }

70
71            int num;
72
73            for (i = 0; i <= 9++i)
74            {
75                num = newnumber % 1000 + i * 1000;
76
77
78                if (i != 0 && mark[num] != 1 && isprimer(num))
79                {
80                    number.push(num);
81                    cnumber[num] = cnumber[newnumber] + 1;
82                    mark[num] = 1;
83                }

84
85                int num1;
86                num1 = newnumber - p * 100 + i * 100;
87
88
89                if (mark[num1] != 1 && isprimer(num1))
90                {
91
92                    number.push(num1);
93                    cnumber[num1] = cnumber[newnumber] + 1
94                    mark[num1] = 1;
95                }

96                int num2;
97                num2 = newnumber - p1 * 10 + i * 10;
98
99
100                if (mark[num2] != 1 &&  isprimer(num2))
101                {
102                    number.push(num2);
103                    cnumber[num2] = cnumber[newnumber] + 1
104                    mark[num2] = 1;
105                }

106
107                int num3 = newnumber / 10 * 10 + i;
108
109                if (mark[num3] != 1 &&  isprimer(num3))
110                {
111                    number.push(num3);
112                    cnumber[num3] = cnumber[newnumber] + 1
113                    mark[num3] = 1;
114                }

115            }

116
117        }

118
119        cout << cnumber[y] << endl;
120
121        n--;
122    }

123
124    return 0;
125}

126
posted on 2009-03-08 11:23 生活要低调 阅读(1301) 评论(1)  编辑 收藏 引用

FeedBack:
# re: POJ 3126 学会广搜队列的用法
2009-03-08 20:25 | cppexplore
removed by cppexplore  回复  更多评论

 < 2009年3月 >
22232425262728
1234567
891011121314
15161718192021
22232425262728
2930311234

•