POJ 3126-Prime Path（BFS-素数变换一位）

太过爱你忘了你带给我的痛 2022-07-12 08:16 134阅读 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;19095</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;10711</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][]

## 题目意思： ##

给两个是素数的四位数（千位始终不为0），每次改变其中一位，使得改变后的数依然是素数，计算从前一个数到后一个数最少一共需要改变几次。

## 解题思路： ##

打表1000~9999中所有的素数。

BFS：队列先将第一个数入队，然后分解出其各个位上的数，循环依次枚举个位~千位，可以是0~9中的任意一个数。

注意每次位数循环维护当前位不变，保证下次循环仅改变下一位上的数。

剪枝：①枚举到与当前位上的数相同的数，②处理过的数。

#include<iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<map>
    #include<algorithm>
    #include<vector>
    #include<queue>
    using namespace std;
    #define INF 0x3f3f3f3f
    #define MAXN 10000
    short int d[4];
    bool prime[MAXN],vis[MAXN];
    int cnt[MAXN];
    void init()//1000~9999中所有的素数
    {
        memset(prime,false,sizeof(prime));
        int i,j;
        for(i=1000; i<=10000; i++)
        {
            for(j=2; j<i; j++)
                if(i%j==0)
                {
                    prime[i]=false;
                    break;
                }
            if(j==i) prime[i]=true;
        }
    }
    int bfs(int a,int b)
    {
        queue <int> q;
        q.push(a);
        vis[a]=true;
        while(!q.empty())
        {
            int s=q.front();
            if(s==b) return cnt[s];
            q.pop();
            d[0]=s%10;//个位
            d[1]=s%100/10;//十位
            d[2]=s%1000/100;//百位
            d[3]=s/1000;//千位
            /*for(int j=3; j>=0; --j)
                cout<<d[j]<<" ";
            cout<<endl;*/
            int temp,x;
            for(int j=0; j<4; ++j) //个位~千位
            {
                x=d[j];//记录当前位置改变之前的数
                for(int i=0; i<10; ++i) //0~9
                {
                    if(x==i) continue;//与当前位相同，剪枝
                    if(j==3&&i==0)continue;//千位不能为0
                    d[j]=i;//改变当前位的数
                    temp=d[3]*1000+d[2]*100+d[1]*10+d[0];
                    if(vis[temp]) continue;//已访问，剪枝
                    if(prime[temp])//是素数
                    {
                        q.push(temp);
                        vis[temp]=true;
                        cnt[temp]=cnt[s]+1;//记录变化次数
                    }
                    if(temp==b) return cnt[temp];
                }
                d[j]=x;//维护当前位不变，保证下次循环仅改变下一位
            }
        }
        return -1;
    }
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("F:/cb/read.txt","r",stdin);
        //freopen("F:/cb/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin>>t;
        init();
        while(t--)
        {
            memset(vis,false,sizeof(vis));
            memset(cnt,0,sizeof(cnt));
            int a,b,ans=0;
            cin>>a>>b;
            ans=bfs(a,b);
            if(ans==-1) cout<<"Impossible"<<endl;
            else cout<<ans<<endl;
        }
        return 0;
    }
    /*
    3
    1033 8179
    1373 8017
    1033 1033
    */

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