POJ 3126 Prime Path
本文最后更新于:2020年6月10日 下午
【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
题目理解
给定两个四位素数,找出从第一个数到第二个数的最短路径长度,规则是:
- 每次只能更改一个数字
- 每次更改之后的数字还是素数
本体需要判定大量四位数字是否是素数,所以可以先用素数筛将范围内的素数筛选出来,这样在变更数字后查询该数字是否为素数是就可以做到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;
}
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!