POJ 3126-Prime Path【搜索】

骑猪看日落 2022-08-20 14:26 17阅读 0赞

F -Prime Path

**Crawling in process...** **Crawling failed**

**Time Limit:** 1000MS **Memory Limit:** 65536KB **64bit IO Format:** %I64d & %I64u

Submit [Status][] [ Practice][Practice] [ POJ 3126][POJ 3126]

Description

![Image 1][]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

解题思路：

题目大意就是给出两个数字，这两个数字是4位的素数，问前一个数变化多少次可以变成后面的数，并且中间变成的还都是素数，问最小的步数。

BFS暴力搜索。

#include<stdio.h>
    #include<cmath>
    #include<queue>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int vis[100000];
    int n,m;
    struct node
    {
    	int x,step;
    };
    queue<node> q;
    
    bool judge_prime(int x) //素数判断 
    {
        if(x == 0 || x == 1)
            return false;
        else if(x == 2 || x == 3)
            return true;
        else
        {
            for(int i = 2; i <= sqrt(x); i++)
                if(x % i == 0)
                    return false;
            return true;
        }
    }
     
    void BFS()
    {
    	int i;
    	node end;
    	while(!q.empty())
    	{
    		end=q.front();
    		q.pop();
    		if(end.x==m)
    		{
    			printf("%d\n",end.step);
    			return ;
    		}
    		end.step++;
    		for(i=1;i<=9;i++)
    		{
    			node wc=end;
    			int s=wc.x/10*10+i;
    			if(s!=wc.x&&!vis[s]&&judge_prime(s))
    			{
    				vis[s]=1;
    				wc.x=s;
    				q.push(wc);	
    			}
    		}
    		for(i=0;i<=9;i++)
    		{
    			node wc=end;
    			int u=wc.x%10;
    			int s=wc.x/100*100+u+i*10;
    			if(s!=wc.x&&!vis[s]&&judge_prime(s))
    			{
    				vis[s]=1;
    				wc.x=s;
    				q.push(wc);
    			}
    		}
    		for(i=0;i<=9;i++)
    		{
    			node wc=end;
    			int u=wc.x%100;
    			int s=wc.x/1000*1000+u+i*100;
    			if(s!=wc.x&&!vis[s]&&judge_prime(s))
    			{
    				vis[s]=1;
    				wc.x=s;
    				q.push(wc);
    			}
    		}
    		for(i=1;i<=9;i++)
    		{
    			node wc=end;
    			int s=wc.x%1000+i*1000;
    			if(s!=wc.x&&!vis[s]&&judge_prime(s))
    			{
    				vis[s]=1;
    				wc.x=s;
    				q.push(wc);
    			}
    		}
    	}
    	printf("Impossible\n");
        return ;
    }
    
    int main()
    {
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{
    		while(!q.empty())
    		q.pop();
    		scanf("%d%d",&n,&m);
    		memset(vis,0,sizeof(vis));
    		node ks;
    		ks.x=n;
    		ks.step=0;
    		vis[n]=1;
    		q.push(ks);
    		BFS();
    	}
    	return 0;
    }

[Status]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=100549#status//F/0
[Practice]: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=15206
[POJ 3126]: http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=15206
[Image 1]: