POJ3126(KB1-F BFS)
2024-10-16 16:25:02
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.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.
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
Source
//2017-02-23
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue> using namespace std; struct node
{
int num, step;
}; bool isPrime(int n)
{
for(int i = ; i*i <= n; i++)
if(n%i==)return false;
return true;
} int pow(int a, int n)
{
int ans = ;
for(int i = ; i < n; i++)
ans *= a;
return ans;
} int main()
{
int n, x, y;
bool book[];
cin>>n;
while(n--)
{
cin>>x>>y;
queue<node> q;
node tmp;
tmp.num = x;
tmp.step = ;
q.push(tmp);
int num, step;
bool ok = false;
memset(book, , sizeof(book));
book[x] = ;
while(!q.empty()){
num = q.front().num;
step = q.front().step;
q.pop();
if(num == y){
ok = true;
cout<<step<<endl;
break;
}
for(int i = ; i < ; i++){
for(int p = ; p < ; p++){
if(i== && p==)continue;
int nowNum = num-((num/pow(, i))%)*pow(, i)+p*pow(, i);
if(!book[nowNum] && isPrime(nowNum)){
tmp.num = nowNum;
tmp.step = step+;
q.push(tmp);
book[nowNum] = ;
}
}
}
if(ok)break;
}
} return ;
}
最新文章
- webpack中字体配置,可以引入bootstrap
- NeHe OpenGL教程 第四十七课:CG顶点脚本
- subsets-ii(需要思考,包括了子数组的求法)
- Eclipse用法和技巧十:显示代码outline
- ThoughtWorks开发持续集成及部署利器:Go
- Velocity(5)——#macro 指令
- php 链接mysql的三种方式对比
- Linux基础入门-Linux下软件安装
- Burp Suite设置代理
- hibernate 嵌套事务
- JavaScript之DOM等级概述
- Session和Cookie,以及用户登录验证问题。
- Zabbix检测Mysql数据库的主从同步
- 将JDBC的resultSet映射到JavaBaen
- centos6.5下安装zip格式的tomcat7和tomcat8,并同时运行
- lintcode-418-整数转罗马数字
- 卸载oracle10g
- quick-cocos2d-x 创建自定义lua绑定c++类
- Swift app中的Crash捕获与处理
- 初识MySQL——人生若如初相逢