第N道的广搜,这几天就准备做广搜了...真的需要好好练习下...
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
这题主要思路就是对每一位进行0-9的改变..第一位不能位0...得到的新数入队...循环直到找到Y
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
6
using namespace::std;
7
8
int cnumber[10000];
9
10
bool mark[10000];
11
12
13
bool 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
27
int 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
生活要低调 阅读(1437)
评论(1) 编辑 收藏 引用