给你n对四位素数，问你从每对中的一个，变成另一个，需要多少步操作，其中每步操作只能改变四位数中的一位，改变之后也必须为素数，并且数字不能以0开始。
开始来一遍埃氏筛法，删选四位数以内的全部素数，然后再进行bfs。代码如下
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>using namespace std;int n, m, T, ans;
bool prime[10000];
int used[10000];struct l{int x;int step;
};int pow(int x, int t)
{int sum = 1;for(int i = 1; i <= t; i++) {sum *= x;}return sum;
}void bfs()
{l f, s;queue<l> q;f.x = n;f.step = 0;q.push(f);while(!q.empty()) {f = q.front();q.pop();if(f.x == m) {ans = f.step;break;}for(int i = 1; i <= 4; i++) {for(int j = 0; j <= 9; j++) {if(i == 4 && !j) {continue;}s.x = f.x / pow(10, i) * pow(10, i) + f.x % pow(10, i - 1) + j * pow(10, i - 1);s.step = f.step + 1;if(!used[s.x] && prime[s.x]) {used[s.x] = 1;q.push(s);}}}}
}int main()
{for(int i = 0; i <= 10000; i++)prime[i] = 1;prime[0] = prime[1] = 0;for(int i = 2; i <= 10000; i++) {if(prime[i]) {for(int j = 2 * i; j <= 10000; j += i) {prime[j] = 0;}}}cin >> T;while(T--) {ans = 0;memset(used, 0, sizeof(used));cin >> n >> m;bfs();cout << ans << endl;}return 0;
}