**链接 : ** Here!
**思路 : ** 素数表 + BFS, 对于每个数字来说, 有四个替换位置, 每个替换位置有10种方案(对于最高位只有9种), 因此直接用 BFS 搜索目标状态即可. 搜索的空间也不大...
/*************************************************************************
> File Name: E.cpp
> Author:
> Mail:
> Created Time: 2017年11月26日 星期日 10时51分05秒
************************************************************************/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
#define MAX_N 100000
int isPrime[MAX_N] = {0}, primeList[MAX_N] = {0};
int T;
int vis[MAX_N];
struct info {
info() {}
info(int num, int step) : num(num), step(step) {}
int num, step;
};
info st, ed;
void init_prime() {
for (int i = 2 ; i < MAX_N ; ++i) {
if (!isPrime[i]) {
primeList[++primeList[0]] = i;
}
for (int j = 1 ; j <= primeList[0] ; ++j) {
if (i * primeList[j] >= MAX_N) break;
isPrime[i * primeList[j]] = 1;
if (i % primeList[j] == 0) break;
}
}
}
// 在num的第i个位置上替换为j
int transInfo(int i, int j, int num) {
int temp[4], k = 3, ret;
while (num) {
temp[k--] = num % 10;
num /= 10;
}
temp[i] = j;
return temp[0] * 1000 + temp[1] * 100 + temp[2] * 10 + temp[3];
}
int check(info p) {
if (p.num < 1000 || p.num >= 10000) return 0;
if (vis[p.num]) return 0;
if (isPrime[p.num]) return 0;
return 1;
}
int BFS() {
queue<info> que;
vis[st.num] = 1;
que.push(st);
while (!que.empty()) {
info now = que.front();
que.pop();
if (now.num == ed.num) {
return now.step;
}
for (int i = 0 ; i < 4 ; ++i) {
for (int j = 0 ; j < 10 ; ++j) {
// 最高位不能为0
if (i == 0 && j == 0) continue;
info temp(transInfo(i, j, now.num), now.step + 1);
if (!check(temp)) continue;
vis[temp.num] = 1;
que.push(temp);
}
}
}
return 0;
}
void solve() {
memset(vis, 0, sizeof(vis));
st.step = 0;
int ret = BFS();
printf("%d\n", ret);
}
int main() {
// freopen("./in.in", "r", stdin);
init_prime();
scanf("%d", &T);
while (T--) {
scanf("%d%d", &st.num, &ed.num);
solve();
}
return 0;
}