质数路径(DAY 99)

1：题目

给定两个四位质数 A 和 B，你需要通过最少的操作次数将 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

2：代码实现

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second

using LL = long long;
using PII = pair<int, int>;

const int N = 2e6 + 10;

PII q[N];
bool st[N], vi[N];

void solve() {
    
    int A, B;
    cin >> A >> B;
    memset(st, false, sizeof st);
    memset(vi, false, sizeof vi);

    auto check = [&](int x) {
    
        for (int i = 2; i * i <= x; i ++)
            if (x % i == 0) return false;
        return true;
    };

    for (int i = 1000; i < 10000; i ++)
        if (check(i)) st[i] = true;

    int hh = 0, tt = -1;
    q[++ tt] = {
    A, 0};
    while (hh <= tt) {
    
        auto t = q[hh ++];
        // cout << t.fi << endl;
        if (t.fi == B) {
    
            cout << t.se << endl;
            return;
        }

        if (vi[t.fi]) continue;
        vi[t.fi] = true;
        int one, two, thr, fou;
        fou = t.fi % 10, thr = (t.fi / 10) % 10;
        two = (t.fi / 100) % 10, one = t.fi / 1000;
        // cout << one << two << thr << fou << endl;
        for (int i = 1; i <= 9; i ++) {
    
            int x = i * 1000;
            x += two * 100 + thr * 10 + fou;
            if (st[x]) q[++ tt] = {
    x, t.se + 1};
        }

        for (int i = 0; i <= 9; i ++) {
    
            int x = one * 1000;
            x += i * 100 + thr * 10 + fou;
            if (st[x]) q[++ tt] = {
    x, t.se + 1};
        }

        for (int i = 0; i <= 9; i ++) {
    
            int x = one * 1000;
            x += two * 100 + i * 10 + fou;
            if (st[x]) q[++ tt] = {
    x, t.se + 1};
        }

        for (int i = 0; i <= 9; i ++) {
    
            int x = one * 1000;
            x += two * 100 + thr * 10 + i;
            if (st[x]) q[++ tt] = {
    x, t.se + 1};
        }
    }
    cout << "Impossible" << endl;
}

signed main() {
    
    int ___ = 1;
    cin >> ___;
    for (; ___ -- ;) solve();
    return 0;
}