题目链接： POJ 3126.Prime Path 题目大意： 找到从素数A转换至素数B的最短方式（A,B都为四位数） 每次转换后的数字必须是四位素数，且每次只能改变四位数中的其中一位。（具体输入等问题请看原题） 样例分析： 1033->1733->3733->3739->3779->8779->8179 测试数据：
Sample Input 3 1033 8179 1373 8017 1033 1033 Sample Output 6 7 0题解思路： 首先英文要判断是否是素数，而且数据还挺大的，所以我们肯定会想到用埃拉托斯特尼筛法（筛法求素数）来求出10000以内的素数表，然后就可以开始用bfs来求解问题了。首先找到bfs每一步的所有去向，根据题目，就是把4个位上的数换成其他的数字，而且还要保证是素数，那么就是列举所有可能的数的替换情况，判断是否是素数然后入队 解决替换数字的问题成为解题关键，我选择分别枚举替换的位数，和替换后的数字然后返回替换后的数值。 这里有两种方法，一是：直接进行数的拆分和合并，（分离出各个位数）二是：运用字符数组然后替换，再转成数值大小。我给出的代码用的是第一种方法。 关于剪枝： 排除以下几种情况：1.第一位不是0 2.最后一位数不是0和2的倍数（偶数不是素数） 3.最后一位不是5和0（不是5的倍数）
最后来看代码： 这里有一个小细节，在我写代码的时候困扰了我很久，因为我并没有排除替换某一位的数为自己，即是替换前后的数值一模一样，但是这一步还是记录了步数，就是最开始输入的数没有变化vis变成了1而不是0，这样就会导致后面的每一步都会多加1。所以后面输出的时候就是x-1。
#include<iostream> #include<vector> #include<queue> #include<cstring> using namespace std; vector<int> p(10000, 1); queue<int> q; int n; int vis[10000]; \\记录步数和判断是否被访问过 void getperm() { \\筛法求素数表 for (int i = 2; i < 10000; i++) { if (p[i] == 1) { for (int j = 2 * i; j < 10000; j+=i) { p[j] = 0; } } } } int change(int b, int n, int c) \\数字替换函数 { switch (n) { case 0: return b % 1000 + c * 1000; case 1: return b / 1000 * 1000 + b % 100 + c * 100; case 2: return b / 100 * 100 + b % 10 + c * 10; case 3: return b / 10 * 10 + c; } } int bfs(int begin,int end) { memset(vis, 0, sizeof(vis)); int next, start; start = begin; vis[start] = 1; q.push(start); while (!q.empty()) { start = q.front(); q.pop(); if (start == end) { return vis[start]; } else { for (int i = 0; i < 4; i++) { for (int j = 0; j <= 9; j++) { if ((i != 0 || j != 0) && (i != 3 || j % 2 != 0 || j!=5)) { next = change(start, i, j); if (p[next] == 1 && !vis[next]) { vis[next] = vis[start] + 1; q.push(next); } } } } } } return -1; } int main() { int begin, end; getperm(); cin >> n; while (n--) { cin >> begin >> end; int x = bfs(begin, end); if (x >= 0) { cout << x - 1<< endl; } else { cout << "Impossible" << endl; } while (!q.empty()) { q.pop(); } } return 0; }