POJ-3126-Prime Path

妖狐艹你老母 2022-01-10 05:09 89阅读 0赞

### 链接：https://vjudge.net/problem/POJ-3126 ###

### 题意： ###

给两个四位数的素数a,b。每次可以改变a的一个值使其成为一个新的四位数素数。

求从a-b的最小操作次数

### 思路： ###

最大10000的素数打表，BFS即可。

### 代码： ###

#include <iostream>
    #include <memory.h>
    #include <queue>
    using namespace std;
    typedef long long LL;
    const int MAXN = 10000;
    int Primes[MAXN];
    int vis[MAXN];
    int vis_Primes[MAXN];
    int Max;
    struct Node
    {
        int _value;
        int _step;
        Node(int value,int step)
        {
            _value = value;
            _step = step;
        }
    };
    
    void init()
    {
        //168 Primes[168-MAXN] > 999
        int pos = 0;
        memset(vis,0,sizeof(vis));
        for (int i = 2;i<MAXN;i++)
        {
            if (vis[i] == 0)
                Primes[pos++] = i;
            for (int j = 0;j < pos&&i*Primes[j] < MAXN;j++)
            {
                vis[i*Primes[j]] = 1;
                if (i%Primes[j] == 0)
                    break;
            }
        }
        Max = pos;
    }
    
    int main()
    {
        init();
        int t,a,b;
        scanf("%d",&t);
        while (t--)
        {
            memset(vis_Primes,0,sizeof(vis_Primes));
            scanf("%d%d",&a,&b);
            queue<Node> que;
            que.push(Node(a,0));
            vis_Primes[a] = 1;
            while (!que.empty())
            {
                int now_value = que.front()._value;
                int now_step = que.front()._step;
                if (now_value == b)
                    break;
                for (int i = 168;i<Max;i++)
                {
                    int flag = 0;
                    int nex = Primes[i];
                    while (now_value)
                    {
                        if (now_value%10 != nex%10)
                            flag++;
                        now_value/=10;
                        nex/=10;
                    }
                    if (flag == 1&&vis_Primes[Primes[i]] == 0)
                    {
                        vis_Primes[Primes[i]] = 1;
                        que.push(Node(Primes[i],now_step+1));
                    }
                    now_value = que.front()._value;
                }
                que.pop();
            }
            printf("%d\n",que.front()._step);
        }
    
        return 0;
    }
    /*
    1
    1033 8179
     */

转载于:https://www.cnblogs.com/YDDDD/p/10268980.html