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 1033Sample Output
6 7 0
1 //
2 // Created by w on 2020/11/5.
3 //
4
5 #include <iostream>
6 #include <queue>
7 #include <cstring>
8 #include <cmath>
9 using namespace std;
10 typedef long long ll ;
11 const int N=10000;
12 int prime[N];
13 bool visit[N];
14 int cnt;
15 struct st
16 {
17 int num;
18 int step;
19 };
20 void Prime()//筛素数,因为题里是4位数，所以从1000-10000的素数筛了出来
21 {
22 int m = sqrt(N + 0.5);
23 for(int i = 2; i <= m; i++)
24 {
25 if(!visit[i])
26 {
27 for(int j = i * i; j <= N; j += i)
28 visit[j] = 1;
29 }
30 }
31 for(int i = 1000; i <= N; i++)
32 {
33 if(!visit[i]) prime[cnt++] = i;
34 }
35 }
36 int ck(int a,int b)
37 {
38 int ans=0,x,y;
39 for(int i=0; i<4; i++)
40 {
41 x=a%10;
42 y=b%10;
43 if(x!=y)
44 ans++;//统计不一样的位数的数字，就是需要购买的
45 a/=10;
46 b/=10;
47 }
48 return ans;
49 }
50 int bfs(int a,int b)
51 {
52 queue<st> q;
53 st a1,b1;
54 a1.num=a;
55 a1.step=0;//step表示步长，需要更换的门牌数字个数
56 q.push(a1);//a1入队
57 while (!q.empty())
58 {
59 b1=q.front();
60 q.pop();
61 if(b1.num==b)
62 return b1.step;
63 for(int i=0; i<cnt; i++)
64 {
65 if(visit[i])//访问过的素数跳过
66 continue;
67 a1.num=prime[i];//是素数保存到a1.num
68 a1.step=b1.step+1;//步长加1
69 int y=ck(b1.num,a1.num);//比较数字不同的位数
70 if(y>1)//一位以上重复执行此过程统计步长
71 continue;
72 else
73 {
74 visit[i]=1;//标记此时这个素数已经被用过
75 if(y==1)//仅有一位不同，会被重新放入队列，进行下一次比较
76 q.push(a1);
77 }
78 }
79 }
80 return -1;//没找到返回-1
81
82 }
83 int main()
84 {
85 int t,m,n;
86 Prime();
87 cin>>t;
88 while (t--)
89 {
90 memset(visit,0,sizeof(visit));//重置visit数组
91 cin>>m>>n;
92 int ans=bfs(m,n);
93 if(ans!=-1)
94 cout<<ans<<endl;
95 else
96 cout<<"Impossible"<<endl;
97 }
98 return 0;
99 }