Prime Path(POJ - 3126)【BFS+筛素数】

KeepZ 2020-10-02 原文

Prime Path(POJ – 3126)

算法

BFS+筛素数打表

1.题目主要就是给定你两个四位数的质数a，b，让你计算从a变到b共最小需要多少步。要求每次只能变1位，并且变1位后仍然为质数。

2.四位数的范围是1000~9999，之间共有1000多个质数。由于已经知道位数为4位，所以可以通过BFS来寻找最小步数。每次需要分别变换个位、十位、百位、千位，并且把符合要求的数放到队列中，同时需标记这个数已经遍历过一次，避免重复遍历，直到找到目标数。

C++代码

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e4;
int primes[N], cnt;
bool st[N];
bool vis[N];
int t, a, b;
struct Number{
    int data;
    int steps;
};
void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j]*i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}
void bfs()
{
    queue<Number> que;
    que.push({a, 0});
    vis[a] = true;
    while(que.size())
    {
        Number cur = que.front();
        que.pop();
        if(cur.data == b)
        {
            cout << cur.steps << endl;
            return ;
        }
        Number tmp;
        /*遍历可能的个位*/
        for(int i = 0; i <= 9; i++)
        {
            tmp.data = cur.data / 10 * 10 + i;
            if(vis[tmp.data] || st[tmp.data]) continue;
            tmp.steps = cur.steps + 1;
            que.push(tmp);
            vis[tmp.data] = true;
        }
        /*遍历可能的十位*/
        for(int i = 0; i <= 9; i++)
        {
            tmp.data = cur.data / 100 * 100 + i * 10 + cur.data % 10;
            if(vis[tmp.data] || st[tmp.data]) continue;
            tmp.steps = cur.steps + 1;
            que.push(tmp);
            vis[tmp.data] = true;
        }
        /*遍历可能的百位*/
        for(int i = 0; i <= 9; i++)
        {
            tmp.data = cur.data % 100 + i * 100 + cur.data / 1000 * 1000;
            if(vis[tmp.data] || st[tmp.data]) continue;
            tmp.steps = cur.steps + 1;
            que.push(tmp);
            vis[tmp.data] = true;
        }
        /*遍历可能的千位*/
        for(int i = 1; i <= 9; i++)
        {
            tmp.data = cur.data % 1000 + i * 1000;
            if(vis[tmp.data] || st[tmp.data]) continue;
            tmp.steps = cur.steps + 1;
            que.push(tmp);
            vis[tmp.data] = true;
        }
    }

}
int main()
{
    get_primes(9999);
    cin >> t;
    while(t--)
    {
        memset(vis, 0, sizeof vis);
        cin >> a >> b;
        bfs();
    }
}