下次自动登录
现在的位置:
& 综合 & 正文
一道简单的BFS题 HDU上 CCNU BFS练习的1003
Prime Path
Time Limit : ms (Java/Other)
Memory Limit : 36K (Java/Other)
Total Submission(s) : 7
Accepted Submission(s) : 5
Problem 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.
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.
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.
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).
One line for each case, either with a number stating the minimal cost or containing the word Impossible.
Sample Input
Sample Output
题目大意就是给你两个四位数数a和b然后a每次可以改变a的个位十位百位或者千位上的一个数字，求出最终得到数字b所需要的最短次数，当然每次改变数字得到的数字需要是一个质数，如果你无论如何都不能在要求每次变换都为质数的约束情况下把a转化为b那么输出Impossible否则求出最短的次数，所以这道题的简单思路就是分别搜索每一次改变的位数之后得到的新数字是不是质数且能不能等于这个目标b的值，如果得到的是质数则次数+1，直到最终得到想要的结果为止，统计累加的次数，然后就是分析怎么优化了，首先它说的是素数，所以应该先用一个BOOL函数来筛选出满足条件的素数，在筛选过程中记得将判定素数的那个循环的复杂度变成根号N以免增加电脑的计算量，筛选素数之后再用BFS进行搜索统计就可以了，依然是利用队列来做，当然对于细节的处理上就是要注意每一位的取值情况，个位必然是奇数，千位得从1开始，十位百位嘛改变时没有特殊要求，不过注意要记得先把十位和个位分离出来啊！唔我用了STL和数组模拟的两种形式把它做出来了下面附上
#include&iostream&
#include&cstring&
#include&queue&
bool check(int n)
for(i=2;i*i&=n;i++)
if(n%i==0)
int num[100005];
int vis[100005];
void bfs()
queue&int&
q.push(a);
while(!q.empty())
int target=q.front();
if(target==b)
cout&&num[b]&&
int k,l,i;
k=target%10;
l=(target/10)%10;
for(i=1;i&=9;i+=2)
int y=(target/10)*10+i;
if(y!=target&&!vis[y]&&check(y))
q.push(y);
num[y]=num[target]+1;
for(i=0;i&=9;i++)
int y=(target/100)*100+i*10+k;
if(y!=target&&!vis[y]&&check(y))
q.push(y);
num[y]=num[target]+1;
for(i=0;i&=9;i++)
int y=(target/+100*i+k+l*10;
if(y!=target&&!vis[y]&&check(y))
q.push(y);
num[y]=num[target]+1;
for(i=1;i&=9;i++)
int y=target%1000+i*1000;
if(y!=target&&!vis[y]&&check(y))
q.push(y);
num[y]=num[target]+1;
cout&&"Impossible"&&
int main()
while(t--)
cin&&a&&b;
memset(vis,0,sizeof(vis));
memset(num,0,sizeof(num));
#include&iostream&
#include&cstring&
bool check(int n)
for(i=2;i*i&=n;i++)
if(n%i==0)
int q[100005];
int vis[100005];
int num[100005];
int front=0,rear=0;
q[front]=a;
while(front&rear)
int target=q[front++];
if(target==b)
cout&&num[b]&&
int k,l,i;
k=target%10;
l=(target/10)%10;
for(i=1;i&=9;i+=2)
int y=(target/10)*10+i;
if(y!=target&&!vis[y]&&check(y))
q[rear++]=y;
num[y]=num[target]+1;
for(i=0;i&=9;i++)
int y=(target/100)*100+i*10+k;
if(y!=target&&!vis[y]&&check(y))
q[rear++]=y;
num[y]=num[target]+1;
for(i=0;i&=9;i++)
int y=(target/+i*100+l*10+k;
if(y!=target&&!vis[y]&&check(y))
q[rear++]=y;
num[y]=num[target]+1;
for(i=1;i&=9;i++)
int y=target%1000+i*1000;
if(y!=target&&!vis[y]&&check(y))
q[rear++]=y;
num[y]=num[target]+1;
cout&&"Impossible"&&
int main()
while(t--)
cin&&a&&b;
memset(vis,0,sizeof(vis));
memset(num,0,sizeof(num));
&&&&推荐文章:
【上篇】【下篇】当前位置：&gt
共找到4261条shimano海淘全球购商品
淘宝全球购为您提供最新最全面的包括美国、日本、澳洲等海外shimano代购，shimano洋货直邮，shimano海外品牌等全球购商品
增值电信业务经营许可证：浙B2-}