Prime Path素数筛与BFS动态规划

朴灿烈づ我的快乐病毒、 2022-01-23 03:37 201阅读 0赞

本文共2053个字，预计阅读时间需要6分钟。

## BFS ##

BFS，其英文全称是Breadth First Search。 BFS并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如队列或是链表），而被检验过的节点则被放置在被称为 closed 的容器中。（open-closed表）

## 素数筛 ##

![在这里插入图片描述][20190602085623688.gif]

[http://www.omegaxyz.com/2019/04/15/e-prime/][http_www.omegaxyz.com_2019_04_15_e-prime]

## 问题 POJ ##

#### 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 ####

3  
1033 8179  
1373 8017  
1033 1033

#### Sample Output ####

6  
7  
0

#### 问题 ####

从一个素数换到另一个素数，每次只能换一个数字（一位）且换后的每次都是素数。求最小次数？

#### C++代码 ####

#include<iostream>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int maxn = 10000;
     
    bool isprime[maxn + 1];
    int dp[maxn + 1];
     
    int getNext(int num, int t, int change){
        
        //num : 当前的数，t当前的位置，change是改变位的值
        if(t == 0) return num / 10 * 10 + change; //最低位
        else if(t == 1) return num /100 * 100 + change * 10 + num % 10;
        else if(t == 2) return num /1000 * 1000 + change * 100 + num % 100;
        else return change * 1000 + num % 1000;
    }
     
    int main(){
        
        fill(isprime+2, isprime + maxn, true);
        for(int i = 2; i <= maxn; i++){
        
            if(isprime[i]){
        
                for(int j = i * i; j <= maxn; j += i){
        
                    isprime[j] = false;
                }
            }
        }//打表
        int T;
        cin>>T;
        while(T--){
        
            int a, b;
            cin>>a>>b;
            fill(dp, dp + maxn, 0x3f);
            dp[a] = 0; //记录从一个prime跳跃到另一个prime所需的最少次数
     
            queue<int> q;
            q.push(a);
            while(!q.empty()){
        
                int cur = q.front(); //取出队列的第一个
                q.pop();
                for(int i = 0; i < 4; i++){
        
                    for(int j = 0; j < 10; j++){
        
                        if(i == 3 && j == 0) continue; //
                        int next = getNext(cur, i, j); //替换
                        if(isprime[next] == false || dp[next] <= dp[cur]) continue;
                        // 不是素数不行，如果到next已经有更小的那也不用这个变换路径了
                        dp[next] = dp[cur] + 1;
                        q.push(next);
                    }
                }
            }
            cout<<dp[b]<<endl;
        }
        return 0;
    }
     
    /* 
    3
    1033 8179
    1373 8017
    1033 1033
     */

[20190602085623688.gif]: /images/20220123/6e6bbd48934b4e7ab9ae746edaeae546.png
[http_www.omegaxyz.com_2019_04_15_e-prime]: http://www.omegaxyz.com/2019/04/15/e-prime/
[omegaxyz.com]: http://omegaxyz.com