Prime Path

落日映苍穹つ 2022-06-01 13:57 184阅读 0赞

Prime Path

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;24392</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;13464</td> 
  </tr> 
 </tbody> 
</table>

Description

![3126_1.jpg][]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

[Northwestern Europe 2006][]

题目大意：就是 给定两个四位素数 a  b ，要求把 a 变换到 b 变换的过程要保证    每次变换出来的数都是一个   四位素数，而且当前这步的变换所得的素数    与    前一步得到的素数   只能有一个数不同，而且每步得到的素数都不能重复。   求从 a 到 b 最少需要的变换次数。无法变换则输出 **Impossible**

**代码：**

#include<stack>
    #include<queue>
    #include<math.h>
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int prime[20000];
    struct node
    {
        int x,y,step;
    } p,q;
    void isprime()//素数打表prime[i]=0为素数
    {
        int i,j;
        memset(prime,0,sizeof(prime));
        prime[1]=1;
        for(i=2; i<20000; i++)
        {
            if(prime[i]==0)
            {
                for(j=2; j*i<20000; j++)
                    prime[j*i]=1;
            }
        }
    }
    int bfs(int s,int e)
    {
        int vis[20000],num;
        memset(vis,0,sizeof(vis));
        queue<node>Q;
        p.x=s;
        p.step=0;
        vis[s]=1;
        Q.push(p);
        while(!Q.empty())//当队列不为空时
        {
            p=Q.front();//取队首
            Q.pop();//清队首
            if(p.x==e)
                return p.step;
            int t[5];
            t[1]=p.x/1000;//记录千位数
            t[2]=p.x/100%10;//记录百位数
            t[3]=p.x/10%10;//记录十位
            t[4]=p.x%10;//记录个位
            for(int i=1;i<=4;i++)
            {
                int temp=t[i];//这里特别注意，每次只能变换一位数，这里用来保存该变换位的数，变换下一位数时，该位数要恢复
                for(int j=0;j<10;j++)
                {
                    if(t[i]!=j)
                    {
                        t[i]=j;
                        num=t[1]*1000+t[2]*100+t[3]*10+t[4];
                    }
                    if(num>=1000&&num<=9999&&!vis[num]&&!prime[num])
                    {
                        q.x=num;
                        q.step=p.step+1;///若满足，步数加1，
                        Q.push(q);
                        vis[num]=1;
                    }
                }
                t[i]=temp;
            }
        }
        return -1;
    }
    int main()
    {
        int test,a,b,ans=0;
        isprime();
        scanf("%d",&test);
        while(test--)
        {
            scanf("%d%d",&a,&b);
            ans=bfs(a,b);
            if(ans!=-1)
                printf("%d\n",ans);
            else
                printf("Impossible\n");
        }
        return 0;
    }

[3126_1.jpg]: /images/20220601/87b239996e6a4f59a82183b6830b4946.png
[Northwestern Europe 2006]: http://poj.org/searchproblem?field=source&key=Northwestern+Europe+2006