题目描述

原题点这里
给定两个四位质数 A 和 ，你需要通过最少的操作次数将 A 变为 B。

每次操作只能改变当前数的其中一位数字，并且每次操作过后，当前数必须仍然是一个质数。

例如，将 1033 变为 8179，最少需要进行 6 次操作，具体操作为：

1033 -> 1733 -> 3733 -> 3739 -> 3779 -> 8779 -> 8179
请计算并输出所需要的最少操作次数。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据占一行，包含两个四位质数 A 和 B。

输出格式
每组数据输出一行答案，表示所需最少操作次数。

如果无法做到，则输出 Impossible。

经实际测试，不存在无解情况，特此声明。

数据范围
1≤T≤100。
1000≤A,B≤9999，
保证 A 和 B 都是质数。

输入样例：
3
1033 8179
1373 8017
1033 1033
输出样例：
6
7
0

BFS+筛质数 $O(t*n)$

普通的bfs，利用to_string和std::stoi()函数来string型和int型的相互转换时间复杂度是常数级。
std::stoi()函数如果不知道可以手写一个转换函数，时间复杂度也是常数级。下面有详细代码。

时间复杂度

get_prime()是线性的，时间复杂度：O(n)，其中n = 10000。
bfs()最多遍历1000-9999的所有数，每次逐位枚举是36次，因此，bfs()的时间复杂度是 O(36 × 10000) = O(360000)，简化为 O(n)，其中 n = 10000。

总时间复杂度： $O(t*n)$，100*10000=1e6

C++ 代码

#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<unordered_map> // 无序map，增删查的速度接近O(1)，而map的速度为O(nlogn)
#include<set>   
#include<queue>

using namespace std;

const int N = 10000 + 10;
int primes[N], cnt; //primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉

void get_prime(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;   //筛掉所有以primes[j]为最小质因数的数
            if (i % primes[j] == 0) break;  //由于是从小到大枚举，故primes[j]一定是i的最小质因子，此时跳出循环
        }
    }
}

// string 转换为 int
int to_int(string s)
{
    int n = s.size();
    int carry = 1000, res = 0;
    for (int i = 0; i <= n; i++) {
        res += carry * (int)(s[i] - '0');
        carry /= 10;
    }

    return res;
}


string a, b;
int dit[N];     // 存储操作次数（距离）

int bfs(string a)
{
    memset(dit, -1, sizeof dit);
    queue<string> q;
    q.push(a);

    dit[to_int(a)] = 0;

    while (q.size()) {
        string t = q.front();
        q.pop();

        if (t == b) return dit[to_int(t)];  // 终点
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 10; j++) {  // 逐位枚举每一位
                if (i == 0 && j == 0) continue; // 防止首位为0
                string tmp = t; // 用于恢复状态
                t[i] = ('0' + j);
                if (!st[to_int(t)] and dit[to_int(t)] == -1) {
                    // 保证t是质数且t没有被搜索过
                    dit[to_int(t)] = dit[to_int(tmp)] + 1;  // 更新距离
                    q.push(t);  // 入队
                }
                t = tmp;    // 恢复状态
            }
        }

    }

    return -1;

}

int main()
{
    get_prime(10000);

    int t = 1;
    cin >> t;
    while (t--) {
        cin >> a >> b;
        cout << bfs(a) << endl;
    }

    return 0;
}