【代码超详解】POJ 3126 Prime Path（质数打表 + BFS）

一、题目描述

第一行输入 n，表示样例个数。
接下来n行每行两个数 s 和 t，单个空格分隔，表示两个质数。
对每一个样例，输出从 s 变换到 t 需要的最小花费。
s 和 t 保证为 1000 到 9999 之间的质数。每次变换只能变换一位，花费 1 英镑。
提示：已经换下来的数字不能再放上去。例如从 1033 变换至 8179：

1033
1733
3733
3739
3779
8779
8179

第二次变换中换下的 1（变成了 3）不能在最后一步中直接放上去，必须要一个额外的 1，这个花费不能省。
如果不能变换，输出：

Impossible

样例：
输入

3
1033 8179
1373 8017
1033 1033

输出

6
7
0

二、算法分析说明与代码编写指导

先套个质数打表的板子，获得 10000 以内的全部质数：

//版本一：
unsigned prime[6542] = { 2,3 }, _PTy, MaxPrime;
inline void genprime(const size_t& _Size) {
	decltype(_PTy) a = 4, t; bool flag;
	for (size_t i = 2; i < _Size;) {
		t = sqrt(a), flag = true;
		for (size_t j = 0; prime[j] <= t; ++j)
			if (a % prime[j] == 0) { flag = false; break; }
		if (flag) { prime[i] = a, ++i; }
		++a;
	}
	MaxPrime = prime[_Size - 1];
}
inline bool isprime(const decltype(_PTy)& x) {
	if (x <= MaxPrime)return binary_search(prime, prime_end, x);
	else {
		decltype(_PTy) t = min((decltype(_PTy))sqrt(x), MaxPrime);
		for (size_t j = 0; prime[j] <= t; ++j)
			if (x % prime[j] == 0)return false;
		return true;
	}
}
//版本二：
unsigned prime[6542] = { 2,3 }, _PTy, MaxPrime, * prime_end = prime + sizeof(prime) / sizeof(prime[0]);
inline void genprime() {
	decltype(_PTy) a = 4, t; bool flag = true;
	for (auto i = prime + 2; i < prime_end;) {
		t = sqrt(a); flag = true;
		for (auto j = prime; *j <= t; ++j)
			if (a % *j == 0) { flag = false; break; }
		if (flag) { *i = a, ++i; }
		++a;
	}
	MaxPrime = *(prime_end - 1);
}
inline bool isprime(const decltype(_PTy)& x) {
	if (x <= MaxPrime)return binary_search(prime, prime_end, x);
	else {
		decltype(_PTy) t = min((decltype(_PTy))sqrt(x), MaxPrime);
		for (auto j = prime; *j <= t; ++j)
			if (x % *j == 0)return false;
		return true;
	}
}

具体解释见：https://blog.csdn.net/COFACTOR/article/details/102993455
当然，这个板子在这题是不能直接用的。因为关键字 auto 和 decltype 都是 C++11 引入的新特性，而上古时代的 POJ 只支持到 C++98：

所以需要先修改再使用。具体见第三部分的 AC 代码。
查表知：10000 以内的质数共 1229 个。

由于质数数量比较少，我们可以直接用一个 bitset 来标记一个数是否为质数，于是质数判定就在 O(1) 的时间复杂度内完成，直接套用板子则是 O(log n)，n 为要判定的数。
下面这一步需要一定的思维能力：要求在最少花费内完成变换，可以抽象为 BFS 求最短路的模型。
图的所有顶点的编号均为质数。因为每次只能变换一位数，所以只有一位不同的两个质数之间连一条无向边。
每次变换一位，花销都相等，所以 BFS 求得最短路径，即得最少花费。
但是，POJ 不仅只支持 C++98 ，而且不开 -O2，这就导致 STL 的速度非常慢。如果借助 STL 来存图，会 TLE。
所以，我们做如下处理：
在 BFS 的过程中再当场判断两点是否连通，即两个质数是否只有一个十进制位不同。如果是，加入队列。如果不是，跳过。
BFS 求最短路的算法的编写过程如下：

BFS求最短路
1、用途：对无权图或矩阵样式的块求最短路径（每步长度相同）。
2、算法内容：
设队列q。先将起点入队，然后以下部分循环直到队列为空，然后输出：
取q的队首，弹出。然后将q周围全部的可走的点都入队。入队的全部点都要立刻标记已访问，以免给出错误结果或死循环。
当队列为空，如果不在终点，则起点到终点无通路；否则，找到了一条最短路径。
3、补充说明：
【1】如果需要输出最短路径需要经过的步数（长度），应该用额外的数组存储已走的步数。当取队首的某一点后，将周围的可行点入队时，
对应位置的步数是刚才队首取到的点的步数+1。

附：获取一个十进制数的各位数的方法

三、AC 代码

#include<cstdio>
#include<algorithm>
#include<bitset>
#include<queue>
#include<cmath>
#pragma warning(disable:4996)
using namespace std;
unsigned prime[1229] = { 2,3 }, * prime_end = prime + sizeof(prime) / sizeof(prime[0]);
bitset<10000> isPrime, visited; unsigned n, r, s, t, S[10000];
inline void genprime() {
	unsigned a = 4, t; bool flag = true;
	for (unsigned* i = prime + 2; i < prime_end;) {
		t = sqrt(a); flag = true;
		for (unsigned* j = prime; *j <= t; ++j)
			if (a % *j == 0) { flag = false; break; }
		if (flag) { *i = a, isPrime[*i] = 1, ++i; }
		++a;
	}
}
inline unsigned BFS(const unsigned& s, const unsigned& t) {
	if (s == t)return 0;
	static queue<unsigned> q; static unsigned a, l, d[4]; while (q.empty() == false)q.pop();
	static const unsigned e[4] = { 1,10,100,1000 };
	q.push(s); visited.reset(); S[t] = 1 << 24; fill(S + 1001, S + 10000, 0);
	while (q.empty() == false) {
		l = S[q.front()] + 1; visited[q.front()] = true;
		for (unsigned i = 0; i <= 3; ++i)d[i] = q.front() / e[i] % 10;
		for (unsigned i = 0; i <= 3; ++i) {
			for (unsigned j = 0; j <= 9; ++j) {
				d[i] = j; if (d[3] == 0)continue;
				a = 1000 * d[3] + 100 * d[2] + 10 * d[1] + d[0];
				if (isPrime[a] == false || visited[a] == true || a == q.front())continue;
				q.push(a); S[a] = l; visited[a] = true;
			}
			d[i] = q.front() / e[i] % 10;
		}
		q.pop();
	}
	return S[t];
}
int main() {
	genprime();
	scanf("%u", &n); ++n;
	while (--n) {
		scanf("%u%u", &s, &t); r = BFS(s, t);
		if (r == 1 << 24)puts("Impossible");
		else printf("%u\n", r);
	}
	return 0;
}