搜索练习题I-09

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

题意：

   给定两个素数（四位数），用一个去找另一个，一次只能改变一个数而且改变完一个数后的数整体还是素数。

思路：

    我发现凡是算最少步数的都是广搜，就用最常规的广搜套路做；

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
int endx,vis[10000],v[10000];//用v[]记录四位数的素数有哪些，做预处理，vis[]记录本数是否算过万一是impossible避免死循环
struct node
{
    int x;
    int step;//记录步数
};
int sushu(int x)//判断素数
{
    for(int i=2;i<=sqrt(x);i++)
    {
        if(x%i==0) return 0;
    }
    return 1;
}
void fuzhu()//算出所有四位数的素数
{
    memset(v,0,sizeof(v));
    for(int i=1000;i<=9999;i++)
    {
        if(sushu(i))
        {v[i]=1;}
    }
}
int bfs(int x)
{
    int a[4],t;
    memset(vis,0,sizeof(vis));//不能忘
    queue<node>an;
    node e;
    e.x=x;e.step=0;
    an.push(e);
    while(!an.empty())
    {
        node s,q;
        s=an.front();//取出
        an.pop();//扔掉
        if(s.x==endx)  return s.step;//找到了
        for(int i=0;i<4;i++)//依次将四个数改变
        {
            a[0]=s.x%10,a[1]=s.x/10%10,a[2]=s.x/100%10,a[3]=s.x/1000;//把四位数拆开
            for(int j=0;j<=9;j++)//变成10个不同的数
            {
                a[i]=j;
                t=a[3]*1000+a[2]*100+a[1]*10+a[0];组合
                if(v[t]&&!vis[t]&&t>1000)//排除将首位数变成0
                {
                    vis[t]=1;//标记
                    q.x=t;
                    q.step=s.step+1;
                    an.push(q);
                }
            }
        }
    }
    return -1;//变不过去
}
int main()
{
    int t,n,k;
    cin>>n;
    fuzhu();
    while(n--)
    {
        cin>>t>>endx;
        k=bfs(t);
        if(k!=-1)
       { cout<<k<<endl;}
        else{cout<<"Impossible"<<endl;}
    }
    return 0;
}