上题解

GPT标准答案：

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

// 判断一个数是否为素数
bool isPrime(int num) {
    if (num < 2) {
        return false;
    }
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

// 判断两个数是否只相差一位
bool isAdjacent(int num1, int num2) {
    int diffCount = 0;
    while (num1 > 0 && num2 > 0) {
        if (num1 % 10 != num2 % 10) {
            diffCount++;
        }
        num1 /= 10;
        num2 /= 10;
    }
    return diffCount == 1;
}

// 寻找从起始数到目标数的最短变化次数
int findMinChange(int start, int target) {
    vector<int> primeNumbers; // 存放4位素数
    vector<int> dist; // 存放变化次数
    queue<int> q; // 广度优先搜索队列
    q.push(start);
    dist.push_back(0);

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        int currentDist = dist.front();
        dist.erase(dist.begin());
        if (current == target) {
            return currentDist;
        }
        for (int i = 0; i <= 9; i++) {
            for (int j = 0; j <= 3; j++) {
                int digit = pow(10, j);
                int changed = current - (current / digit % 10) * digit + i * digit;
                if (isPrime(changed) && isAdjacent(current, changed)) {
                    bool isNewNumber = true;
                    for (int k = 0; k < primeNumbers.size(); k++) {
                        if (changed == primeNumbers[k]) {
                            isNewNumber = false;
                            break;
                        }
                    }
                    if (isNewNumber) {
                        q.push(changed);
                        primeNumbers.push_back(changed);
                        dist.push_back(currentDist + 1);
                    }
                }
            }
        }
    }
    return 0;
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int a, b;
        cin >> a >> b;
        int minChange = findMinChange(a, b);
        cout << minChange << endl;
    }
    return 0;
}