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
3
1033 8179
1373 8017
1033 1033
Sample Output
6
7
0
分析
mdzz,这题犯了几个傻逼错误,写到半夜…每次转换应该是素数的,我开始也是这样想的,但中间因为 tmp=num[i]; num[i]=tmp;没有写,让我怀疑是不是每次转换不一定是素数,然后查了下素数表,神奇的是我当时查的时候没看见,以为不一定是素数,后来把刚才那个bug改了,能搜出来,但输出数字不对,然后又tm查素数表,居然查到了(:з」∠)。 我查了假表,做了假题…..
经修饰的代码
/*************************************************************************
> File Name: poj3126.cpp
> Author:LaPucelle
> Mail:
> Created Time: 2017年01月21日 星期六 23时41分38秒
************************************************************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<string>
#include<cstring>
#include<vector>
#include<set>
#include<list>
#include<map>
#include<queue>
#define rep(i,a,b) for(int i=(a);i<=(b);(i++))
#define inf 0x3fff3f
#define ll long long
#define pi acos(-1)
int dire[4][2]={ {0,1},{1,0},{0,-1},{-1,0} };
int dire2[8][2]={{-1,-1},{-1,0},{-1,1},{ 0,-1},{ 0,1},{ 1,-1},{ 1,0},{ 1,1}};
int dire3[6][3]={ {0,0,1},{0,1,0},{1,0,0},{0,0,-1},{0,-1,0},{-1,0,0} };
using namespace std;
const int maxn=10000;
int prime[maxn];
int vis[maxn];
//判断是否为素数
inline int isprime(int n){
int now=0;
for(int i=2;i*i<=n;i++){
if(n%i==0){
now=1;
break;
}
}
if(now)
return 0;
return 1;
}
// 打表
int gene(int l,int r){
for(int i=l;i<=r;i++){
if(isprime(i)){
prime[i]=1;
}
}
}
int step[maxn];//记录走的步数
// bfs
void bfs(int n,int m){
queue<int> q;
q.push(n);
step[n]=0;
vis[n]=1;
while(!q.empty() ){
int head=q.front();
q.pop();
if(head==m){
printf("%d\n",step[m]);
return;
}
int num[5];
num[1]=head/1000;
num[2]=head/100%10;
num[3]=head/10%10;
num[4]=head%10;
int next;
for(int i=4;i>=1;i--){
int j;
if(i==1)
j=1;
else
j=0;
int tmp=num[i];
for(;j<=9;j++){
num[i]=j;
next=num[1]*1000+num[2]*100+num[3]*10+num[4];
if( prime[next] && !vis[next]){
vis[next]=1;
q.push(next);
step[next]=step[head]+1;
}
}
num[i]=tmp; //容易错的地方
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
memset(prime,0,sizeof(prime));
gene(1000,9999);
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
memset(vis,0,sizeof(vis));
memset(step,0,sizeof(step));
bfs(n,m);
}
return 0;
}
debug的代码(未修改)
/*************************************************************************
> File Name: poj3126.cpp
> Author:LaPucelle
> Mail:
> Created Time: 2017年01月21日 星期六 23时41分38秒
************************************************************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<string>
#include<cstring>
#include<vector>
#include<set>
#include<list>
#include<map>
#include<queue>
#define rep(i,a,b) for(int i=(a);i<=(b);(i++))
#define inf 0x3fff3f
#define ll long long
#define pi acos(-1)
int dire[4][2]={ {0,1},{1,0},{0,-1},{-1,0} };
int dire2[8][2]={{-1,-1},{-1,0},{-1,1},{ 0,-1},{ 0,1},{ 1,-1},{ 1,0},{ 1,1}};
int dire3[6][3]={ {0,0,1},{0,1,0},{1,0,0},{0,0,-1},{0,-1,0},{-1,0,0} };
using namespace std;
const int maxn=10000;
int prime[maxn];
int vis[maxn];
inline int isprime(int n){
int now=0;
for(int i=2;i*i<=n;i++){
if(n%i==0){
now=1;
break;
}
}
if(now)
return 0;
return 1;
}
int gene(int l,int r){
for(int i=l;i<=r;i++){
if(isprime(i)){
prime[i]=1;
}
}
}
int step[maxn];
void bfs(int n,int m){
queue<int> q;
q.push(n);
step[n]=0;
vis[n]=1;
int now=0;
while(!q.empty() ){
int head=q.front();
q.pop();
//printf("@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\nnow=%d\n",now);
//printf("head=%d\n",head);
/*
if(head==1033){
printf("now=%d\n",now);
printf("step=%d\n",step[head]);
printf("%d\n",1033);
}
if(head==1733){
printf("now=%d\n",now);
printf("step=%d\n",step[head]);
printf("%d\n",1733);
}
if(head==3733){
printf("now=%d\n",now);
printf("step=%d\n",step[head]);
printf("%d\n",3733);
}
if(head==3739){
printf("now=%d\n",now);
printf("step=%d\n",step[head]);
printf("%d\n",3739);
}
if(head==3779){
printf("now=%d\n",now);
printf("step=%d\n",step[head]);
printf("%d\n",3779);
}
if(head==8779){
printf("now=%d\n",now);
printf("step=%d\n",step[head]);
printf("%d\n",8779);
}
if(head==8179){
printf("now=%d\n",now);
printf("step=%d\n",step[head]);
printf("%d\n",8179);
}
*/
if(head==m){
//printf("hello world\n");
printf("%d\n",step[m]);
return;
}
int num[5];
num[1]=head/1000;
num[2]=head/100%10;
num[3]=head/10%10;
num[4]=head%10;
/*
for(int i=1;i<=4;i++)
printf("%d ",num[i])
*/
int next;
for(int i=4;i>=1;i--){
int j;
if(i==1)
j=1;
else
j=0;
int tmp=num[i];
for(;j<=9;j++){
num[i]=j;
next=num[1]*1000+num[2]*100+num[3]*10+num[4];
if( prime[next] && !vis[next]){
//printf("next=%d",next);
/*
if(next==m){
printf("nico nico ni\n");
for(int k=1;k<=4;k++)
printf("%d",num[k]);
printf("\n");
//printf("%d",step[head]+1);
}
*/
vis[next]=1;
q.push(next);
step[next]=step[head]+1;
}
}
num[i]=tmp;
}
now++;
}
}
int main()
{
//std::ios::sync_with_stdio(false);
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
memset(prime,0,sizeof(prime));
gene(1000,9999);
/*
printf("prime[1033]=%d\n",prime[1033]);
printf("prime[8179]=%d\n",prime[8179]);
*/
/*
for(int i=1000;i<=9999;i++)
if(prime[i]==1)
printf("%d\n",i);
*/
int t;
cin>>t;
int count=1;
while(t--){
//printf("case %d\n",count++);
int n,m;
cin>>n>>m;
memset(vis,0,sizeof(vis));
memset(step,0,sizeof(step));
bfs(n,m);
}
return 0;
}