POJ Prime Path 埃氏筛法+广度优先搜索

思路：用埃氏筛法打个表，然后bfs即可

#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
ll inf = 0x3f3f3f3f3f3f3f3f;
bool isPrime[10007];
ll d[10007];
int tenPow[10];
int mint;
void initTenPow()
{tenPow[0] = 1;for (int i = 1; i <= 7; i++){tenPow[i] = tenPow[i - 1] * 10;}
}
void sieve()
{for (int i = 0; i <= 10000; i++){isPrime[i] = true;}isPrime[0] = false, isPrime[1] = false;for (int i = 1; i * i <= 10000; i++){if (!isPrime[i]){continue;}for (int j = 2 * i; j <= 10000; j += i){isPrime[j] = false;}}
}
void init()
{for (int i = 1000; i <= 9999; i++){d[i] = inf;}
}
void bfs(int start)
{queue<int> que;que.push(start);d[start] = 0;while (!que.empty()){int p = que.front();que.pop();for (int i = 1; i <= 4; i++){for (int j = 0; j <= 9; j++){if (i == 1 && j == 0){continue;}int q = (p / tenPow[5 - i]) * tenPow[5 - i] + (j * tenPow[4 - i]) + (p % tenPow[4 - i]);if (isPrime[q] && d[p] + 1 < d[q]){d[q] = d[p] + 1;que.push(q);}}}}
}
int main()
{initTenPow();sieve();int t, p, q;scanf("%d", &t);while (t--){init();scanf("%d%d", &p, &q);bfs(p);printf("%lld\n", d[q]);}return 0;
}