Prime Path（POJ 3126）解题报告
一、原题
Prime Path
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
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.
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
31033 81791373 80171033 1033
Sample Output
670
二、题目大意：
输入两个四位素数，计算将第一个素数转化为第二个素数所需要的最短步数。
要求：
1、每次转化只能swap一个数字，而且用过的数字不能再用
2、每次转化的结果也必须是一个素数
三、基本思路：
1、第一个素数用char数组存储，第二个用int存储，用字符串存储对单个位操作时更加便捷（使用了<cstdlib>中的atoi(str1)函数，可将字符串直接转换成长整型整数）。
2、一开始用了struct 来存储
struct P
{
int num;//结构体里存的x代表当前的操作数是几，t代表已经操作了几次
int t;
};
大概到第四层很快溢出、、、、囧~
由于用结构体溢出（囧~），这里改用一个step[10000]记录到i个数时当前步数。visited[10000]存储该数字是否被访问过（题目大意1）.
3、素数表生成函数
int prime[10000];//素数表
void primeTable()//素数表生成
{
memset(prime,0,sizeof(prime));
prime[0] = 1;
prime[1] = 1;
int i,j;
for(i = 2 ; i < 10000 ; ++i)
{
if(!prime[i])
for(j = i*i ; j <= 10000 ; j += i) prime[j] = 1;//为1为合数，挖掉质数的平方
}
}
4、用一个int队列存数，将队列顶部元素以字符串形式再度存入num1。
status temp_int=que.front();
char temp_str[5];
num1[0]='0'+temp_int/1000;
num1[1]='0'+(temp_int/100)%10;
num1[2]='0'+(temp_int/10)%10;
num1[3]='0'+temp_int%10;
num1[4]='\0';
Ps：最后一句十分关键，由于丢掉这句导致T溢出，需要了解的是strcpy函数根据指针进行赋值，因此最后必须加上\0作为结尾标记。
5、BFS关键代码部分：
这部分的嵌套循环实质是对一个数，num1（起始素数）先向上遍历，再向下遍历，找到下一层素数。。（注意向下遍历时需要防止出现0999现象）
for(int i=0; i<4; i++)
{
for(int j=num1[i]+1; j<='9'; j++)
{
strcpy(temp_str,num1);
temp_str[i]=j;
status p1= atoi(temp_str);
if(!visited[p1]&&!prime[p1])//若没被访问过，且新生成的数字temp_str是一个素数
{
visited[p1]=true;
step[p1]=step[temp_int]+1;
que.push(p1);//压入下一层素数
}
}
for(int j=num1[i]-1; j>='0'; j--)
{
//其他部分上下均与上一个for相同，只是在if前加上了下面这句
if(p1<1000) break;//非常关键，避免出现0999现象
}
}
四、源码完整版
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdlib>//atoi头文件
#include <queue>
#include <cstdio>
using namespace std;
int step[10000];//记录到i个数时当前步数
int prime[10000];//素数表
bool visited[10000];//一共可能遇到9999-1000个数，只能被访问一次
void primeTable()//素数表生成
{
memset(prime,0,sizeof(prime));
prime[0] = 1;
prime[1] = 1;
int i,j;
for(i = 2 ; i < 10000 ; ++i)
{
if(!prime[i])
{
for(j = i*i ; j <= 10000 ; j += i)
{
prime[j] = 1;
}
}
}
}
typedef int status;
int main()
{
char num1[5];//num1用字符数组存储！
int num2,T1,ans;
primeTable();
cin>>T1;
while(T1--)
{
cin>>num1>>num2;
if(atoi(num1)==num2)
{
cout<<0<<endl;
continue;
}
memset(visited,0,sizeof(visited));
memset(step,0,sizeof(step));
ans=0;
bool flag=false;//表示找到了结果
queue<status>que;
que.push(atoi(num1));//p0压入队列
while(!que.empty())
{
status temp_int=que.front();
char temp_str[5];
num1[0]='0'+temp_int/1000;//取出各位存入num1
num1[1]='0'+(temp_int/100)%10;
num1[2]='0'+(temp_int/10)%10;
num1[3]='0'+temp_int%10;
num1[4]='\0';
visited[temp_int]=true;
que.pop();
if(temp_int==num2)
{
flag=true;
cout<<step[num2]<<endl;
break;
}
for(int i=0; i<4; i++)
{
for(int j=num1[i]+1; j<='9'; j++)
{
strcpy(temp_str,num1);
temp_str[i]=j;
status p1= atoi(temp_str);
if(!visited[p1]&&!prime[p1])//如果没有被访问过而且新生成的数字temp_str是一个素数
{
visited[p1]=true;
step[p1]=step[temp_int]+1;
que.push(p1);
}
}
for(int j=num1[i]-1; j>='0'; j--)
{
strcpy(temp_str,num1);
temp_str[i]=j;
status p1= atoi(temp_str);
if(p1<1000) break;
if(!visited[p1]&&!prime[p1])//如果没有被访问过而且新生成的数字temp_str是一个素数
{
visited[p1]=true;
step[p1]=step[temp_int]+1;
que.push(p1);
}
}
}
}
if(!flag)
cout<<"Impossible"<<endl;
}
return 0;
}
PS：下完之后发现那个flag好像可以不用的。。。。囧，解题报告处女作，就这样吧， 其实我就是A不下去了
另，附上链接：
http://poj.org/problem?id=3126