【代码源】 每日一题 素数之欢（bfs）

2022.4.27

题目链接：素数之欢 - 题目 - Daimayuan Online Judge

题目描述

现给定两个 四位素数 a,b。 你可以执行多次下面的操作：

修改数字 aa 的某一位, 使其成为另一个 四位素数。

例如，1033→1733，其中 1033 与 1733 均为素数。

问至少多少次变换后能从 a 得到 b ? 或回答不可能。

数据规模

• 多组数据 1≤T≤100

输入格式

第一行一个数字 T，表示接下来将会有 T 组数据。

接下来包含 T 行，每行包含用空格分开的两个 四位素数 a,b。

输出格式

输出 T 行，如果可以，输出最小变换次数。反之输出 −1。

 

题目给出两个四位数的素数，求a变换为b最少需要几次，若不能成功变换则输出-1.

首先，毫无疑问肯定得先预处理1000~9999是否为素数。  

本题可以构图连边求最短路径，但因为此题边权为1，为无权无向图，考虑用bfs会稍微更快些。根据宽搜的性质，最先搜到的一定是最优解，所以当搜到目标数便可以直接返回输入答案。当队列为空也未搜到则输出-1。

详见代码 

#include <bits/stdc++.h>
using namespace std;
bool isprime[10009], used[10009]; // isprime为0表示为素数，used表示是否入队
int cnt[10009];                   //记录步数
void preinit()//预处理1000~9999是否为素数
{
    isprime[0] = isprime[1] = 1;
    for (int i = 2; i < 10000; i++)
    {
        if (isprime[i] == 0)
        {
            for (int j = 2 * i; j < 10000; j += i) //标记质数i的倍数为1，即不是素数
            {
                isprime[j] = 1;
            }
        }
    }
}
int bfs(int x, int y)
{
    memset(cnt, 0, sizeof(cnt)); //清零
    memset(used, 0, sizeof(used));
    int a, b, c, d;
    queue<int> q;
    q.push(x);
    while (!q.empty())
    {
        int temp = q.front();
        q.pop();
        if (temp == y) //找到终点，返回步数即最小步数
        {
            return cnt[y];
        }
        a = temp % 10;               //个位
        b = temp % 100 / 10;         //十位
        c = temp % 1000 / 100;       //百位
        d = temp / 1000;             //千位
        for (int i = 0; i <= 9; i++) //枚举下一个数（改变个位）
        {
            if (i == a) //与原数重复
                continue;
            int num = i + b * 10 + c * 100 + d * 1000;
            if (isprime[num] == 0 && used[num] == 0) // num为素数且未入过队
            {
                cnt[num] = cnt[temp] + 1; // num可以由temp变换而来
                used[num] = 1;            //标记
                q.push(num);              //入队
            }
        }
        for (int i = 0; i <= 9; i++) //枚举下一个数（改变十位）
        {
            if (i == b)
                continue;
            int num = a + i * 10 + c * 100 + d * 1000;
            if (isprime[num] == 0 && used[num] == 0)
            {
                cnt[num] = cnt[temp] + 1;
                used[num] = 1;
                q.push(num);
            }
        }
        for (int i = 0; i <= 9; i++) //枚举下一个数（改变百位）
        {
            if (i == c)
                continue;
            int num = a + b * 10 + i * 100 + d * 1000;
            if (isprime[num] == 0 && used[num] == 0)
            {
                cnt[num] = cnt[temp] + 1;
                used[num] = 1;
                q.push(num);
            }
        }
        for (int i = 1; i <= 9; i++) //枚举下一个数（改变千位），从1开始是因为不能有前导零
        {
            if (i == d)
                continue;
            int num = a + b * 10 + c * 100 + i * 1000;
            if (isprime[num] == 0 && used[num] == 0)
            {
                cnt[num] = cnt[temp] + 1;
                used[num] = 1;
                q.push(num);
            }
        }
    }
    return -1; //队列为空也未找到终点，则无法变换得到返回-1
}
int main()
{
    preinit();
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        cout << bfs(a, b) << "\n"; //输出
    }
}