POJ - 3126 - Prime

先上题目

Prime Path

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 9259		Accepted: 5274

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

Sample Output

6

7

0

　 题意比较简单，就是给你两个4位的素数，问你能不能经过有限的步骤将第一个素数转化为第二个素数，其中转化的要符合一下的要求：每一次只可以改变这个四位数的某一位，首位不能为0，每一次转化以后得到的数要还是素数。如果不可以转化得到目标素数，输出Impossible。
　 做法也是比较简单，先筛出10000以内的素数出来，然后枚举当前的这个素数可以转化的其他素数，然后进行bfs，当遇到目标素数的时候就输出步数；如果转化不了就会把可以转化的素数都转化了一遍，最后循环就会结束。这里为了能够判断是否能转化，需要标记它转化过哪些素数，转化过的素数如果再出现，就不需要再搜索这个数了。

上代码：

 #include <stdio.h>

 #include <string.h>

 #include <queue>

 #include <map>

 #define LL long long

 #define MAX (10000+10)

 using namespace std;

 bool f[MAX],M[MAX];

 typedef struct

 {

     int l;

     int st;

 }S;

 queue<S> q;

 void dedeal()

 {

     LL i,j,n;

     n=MAX;

     for(i=;i<=n;i++)

     {

         if(!f[i])

         {

             for(j=i*i;j<=n;j+=i)  f[j]=;

         }

     }

 }

 int check(int x,int y)

 {

     int t,i;

     S d;

     d.l=x;

     d.st=;

     memset(M,,sizeof(M));

     while(!q.empty()) q.pop();

     q.push(d);

     M[d.l]=;

     while(!q.empty())

     {

         d=q.front();

         q.pop();

         if(d.l==y) return d.st;

         d.st++;

         x=d.l;

         t=x/*;

         for(i=;i<;i++)

         {

             d.l=t+i;

             if(!f[d.l] && d.l!=x && !M[d.l])

             {

                 M[d.l]=;

                 q.push(d);

             }

         }

         t=x/*+x%;

         for(i=;i<;i+=)

         {

             d.l=t+i;

             if(!f[d.l] && d.l!=x && !M[d.l])

             {

                 M[d.l]=;

                 q.push(d);

             }

         }

         t=x/*+x%;

         for(i=;i<;i+=)

         {

             d.l=t+i;

             if(!f[d.l] && d.l!=x && !M[d.l])

             {

                 M[d.l]=;

                 q.push(d);

             }

         }

         t=x%;

         for(i=;i<;i+=)

         {

             d.l=t+i;

             if(!f[d.l] && d.l!=x && !M[d.l])

             {

                 M[d.l]=;

                 q.push(d);

             }

         }

     }

     return -;

 }

 int main()

 {

     int n,c,x,y;

     //freopen("data.txt","r",stdin);

     dedeal();

     scanf("%d",&n);

     while(n--)

     {

         scanf("%d %d",&x,&y);

         c=check(x,y);

         if(c==-) printf("Impossible\n");

         else printf("%d\n",c);

     }

     return ;

 }

3126

巴特西

POJ - 3126 - Prime

最新文章

热门文章