Prime Path
| Time Limit: 1000MS |
|
Memory Limit: 65536K |
| Total Submissions: 6751 |
|
Accepted: 3830 |
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
就是找从a到b的路径，每次只能换一个数字，要求路径上的数字必须为质数
我傻逼了，我改了老半天也没改对
最后忽然发现，我bfs的时候都已经赋好初值了，结果又memset了一遍，悲剧啊，浪费了我那么长时间
1
#include<stdio.h>
2#include<string.h>
3#include<math.h>
4int a,b,ans;
5int q[10005];
6int num[10005];
7int flag[10005];
8int check(int nn1)
9
{
10
int i;
11 if(nn1==0||nn1==1) return 0;
12 for(i=2; i<=(int)(sqrt(nn1)); i++)
13 if(nn1%i==0) return 0;
14 return 1;
15
}
16int make(int i,int j,int now1)
17{
18 int tmp;
19 tmp=0;
20 switch (i)
21
{
22 case 1:
23 {
24 if(j==0) return 0;
25 tmp=j*1000+now1%1000;
26 return tmp;
27
}
28 case 2:
29 {
30 tmp=(now1/1000)*1000+j*100+now1%100;
31 return tmp;
32 }
33 case 3:
34 {
35 tmp=(now1/100)*100+j*10+now1%10;
36 return tmp;
37 }
38 case 4:
39 {
40 if (now1&1==0)
41 {
42 return -1;
43 }
44 tmp=now1-now1%10+j;
45 return tmp;
46 }
47 }
48}
49int getit(int i,int xx)
50{
51 switch (i)
52 {
53 case 1:
54 {
55 return xx/1000;
56 }
57 case 2:
58 {
59 return (xx/100)%10;
60 }
61 case 3:
62 {
63 return (xx/10)%10;
64 }
65 case 4:
66 {
67 return xx%10;
68 }
69 }
70}
71int bfs()
72{
73 int head,tail,now,i,j,tmp1;
74 int nn;
75 memset(q,0,sizeof(q));
76 memset(num,0,sizeof(num));
77 memset(flag,0,sizeof(flag));
78 head=0;
79 tail=1;
80 q[1]=a;
81 flag[a]=1;
82 num[1]=0;
83 while(head<tail)
84 {
85 head++;
86 now=q[head];
87 for(i=1; i<=4; i++)
88 {
89 tmp1=getit(i,now);
90 for(j=0; j<=9; j++)
91 {
92 if(j!=tmp1)
93 nn=make(i,j,now);
94 if (nn!=0)
95 if (!flag[nn])
96 if(check(nn))
97 {
98 if(nn==b)
99 {
100 return num[head]+1;
101 }
102 flag[nn]=1;
103 tail++;
104 q[tail]=nn;
105 num[tail]=num[head]+1;
106 }
107 }
108 }
109 }
110}
111int main()
112{
113 int t,i;
114 scanf("%d",&t);
115 for(i=1; i<=t; i++)
116 {
117 scanf("%d%d",&a,&b);
118 if(a==b)
119 {
120 printf("0\n");
121 }
122 else
123 {
124 ans=bfs();
125 printf("%d\n",ans);
126 }
127 }
128 return 0;
129}
130