【POJ】 3126 Prime Path

题目链接：poj-3126

Description

The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
Now, the minister of finance, who had been eavesdropping, intervened. — No unnecessary expenditure, please! I happen to know that the price of a digit is one pound. — Hmm, in that case I need a computer program to minimize the cost. You don’t know some very cheap software gurus, do you? — In fact, I do. You see, there is this programming contest going on… Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.

1033 
1733 
3733 
3739 
3779 
8779 
8179

The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

---

Input

One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).

---

Output

One line for each case, either with a number stating the minimal cost or containing the word Impossible.

---

Sample Input

3
1033 8179
1373 8017
1033 1033

---

Sample Output

6
7
0

---

题目理解

​ 给定两个四位素数，找出从第一个数到第二个数的最短路径长度，规则是：

1. 每次只能更改一个数字
2. 每次更改之后的数字还是素数

​ 本体需要判定大量四位数字是否是素数，所以可以先用素数筛将范围内的素数筛选出来，这样在变更数字后查询该数字是否为素数是就可以做到O(1)的时间复杂度。

​ 寻找最短路径长度，使用BFS。

---

代码

#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int MAXN = 10001;

struct primeth{		//答案要求的是路径长度，都BFS过程中需要记录素数数值(num)以及路径长度(ans) 
	int num;
	int ans;
	primeth(int num, int ans) : num(num), ans(ans){}
};

int a, b, cnt, n;
int primes[MAXN];
bool flag[MAXN], vis[MAXN];
queue<primeth> q;

//欧拉筛 (详细解释见上篇博客)
void prime(){
	cnt = 0;
	memset(flag, false, MAXN);
	for(int i = 2; i < MAXN; ++i){
		if(!flag[i])
			primes[cnt++] = i;
		for(int j = 0; j <= cnt; ++j){
			if(i * primes[j] > MAXN) break;
			flag[i * primes[j]] = true;
			if(i % primes[j] == 0) break;
		}
	}
} 

int BFS(){
	q.push(primeth(a, 0));
	primeth tmp = q.front();
	while(!q.empty()){
		if(tmp.num == b) 
			return tmp.ans;
		primeth front = q.front();
		q.pop();
		tmp.ans = front.ans + 1;
		for(int i = 0; i <= 9; ++i){	//这个循环是用来改变素数的各个位的数值的，写得比较麻烦，有更好的写法欢迎评论 
			if(i){
				tmp.num = front.num % 1000 + 1000 * i;
				if(vis[tmp.num] && !flag[tmp.num]){
					if(tmp.num == b) 
						return tmp.ans;
					q.push(tmp);
				}
				vis[tmp.num] = false;
			}
			for(int j = 1; j <= 3; ++j){
				tmp.num = front.num - (int)(front.num % (int)pow(10, j) / pow(10, j - 1)) * pow(10, j - 1) + pow(10, j - 1) * i;
				if(vis[tmp.num] && !flag[tmp.num]){
					if(tmp.num == b) 
						return tmp.ans;
					q.push(tmp);
				}
				vis[tmp.num] = false;
			}
		}
	}
}

int main(){
	prime();
	cin >> n;
	while(n--){
		memset(vis, true, MAXN);
		while(!q.empty()) q.pop(); 
		cin >> a >> b;
		vis[a] = false;
		cout << BFS() << endl;
	}
	
	return 0;
}