# 【POJ】 3126 Prime Path

## 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;
}``````