POJ3126 Prime Path

电玩女神 2021-10-01 01:10 251阅读 0赞

**题目：**

***给你两个四位的素数a，b。  
a可以改变某一位上的数字变成c，但只有当c也是四位的素数时才能进行这种改变。  
请你计算a最少经过多少次上述变换才能变成b。  
例如：1033 -> 8179   
1033   
1733   
3733   
3739   
3779   
8779   
8179  
最少变换了6次。***

**输入：**

***第一行输入整数T，表示样例数。 (T <= 100)   
每个样例输入两个四位的素数a，b。(没有前导零) ***

**输出：**

***对于每个样例，输出最少变换次数，如果无法变换成b则输出"Impossible"。***

**样例：**

**![1706379-20190604110609510-776533724.png][]**

**分析：**stoi不能用（RE），还有atoi，itoa（我编译环境（manjaro+Clion）下用不了）  
用的stringstream

#include<iostream>
    #include<sstream>
    #include<cstdio>
    #include<cstdlib>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include<functional>
    #include<iomanip>
    #include<numeric>
    #include<cmath>
    #include<queue>
    #include<vector>
    #include<set>
    #include<cctype>
    #define PI acos(-1.0)
    const int INF = 0x3f3f3f3f;
    const int NINF = -INF - 1;
    typedef long long ll;
    using namespace std;
    bool isp[10005];
    bool used[10005];
    string x, y;
    void isprime()
    {
        memset(isp, true, sizeof(isp));
        for (int i = 4; i < 10000; i += 2)
            isp[i] = false;
        for (int i = 2; i < 10000; ++i)
        {
            if (isp[i])
            {
                for (int j = i * i; j < 10000; j += i)
                    isp[j] = false;
            }
        }
    }
    //int t = 0;
    int bfs()
    {
        queue<string> q;
        q.push(x);
        int d[10005];
        memset(d, INF, sizeof(d));
        stringstream s1;
        s1 << x;
        int num1;
        s1 >> num1;
        d[num1] = 0;
        while (q.size())
        {
            string temp = q.front();
            q.pop();
            if (temp == y) break;
            stringstream s2;
            s2 << temp;
            int nx;
            s2 >> nx;
            //cout << nx << endl;
            //cout << endl;
            for (int i = 0; i < 4; ++i)
            {
                int r;
                if (i == 0) r = nx / 1000;
                else if (i == 1) r = nx / 100 % 10;
                else if (i == 2) r = nx / 10 % 10;
                else r = nx % 10;
                //cout << r << endl;
                for (int j = 0; j < 10; ++j)
                {
                    if (j == 0 && i == 0) continue;
                    if (j == r) continue;
                    //cout << '*' << j << endl;
                    int num;
                    if (i == 0) num = j * 1000 + nx % 1000;
                    else if (i == 1) num = nx / 1000 * 1000 + j * 100 + nx % 100;
                    else if (i == 2) num = nx / 100 * 100 + j * 10 + nx % 10;
                    else num = nx / 10 * 10 + j;
                    //cout << num << endl;
                    if (isp[num] && !used[num])
                    {
                        //t++;
                        used[num] = true;
                        d[num] = d[nx] + 1;
                        string s;
                        stringstream ss;
                        ss << num;
                        ss >> s;
                        q.push(s);
                    }
                }
            }
        }
        //cout << t << endl;
        stringstream s3;
        s3 << y;
        int num3;
        s3 >> num3;
        return d[num3];
    }
    int main()
    {
        int T;
        cin >> T;
        isprime();
        while (T--)
        {
            cin >> x >> y;
            memset(used, false, sizeof(used));
            int num = bfs();
            if (num == INF) cout << "Impossible" << endl;
            else cout << num << endl;
        }
        return 0;
    }

转载于:https://www.cnblogs.com/veasky/p/10972363.html

[1706379-20190604110609510-776533724.png]: /images/20210724/57d6a586735841bfa05660633eb23841.png