方老师与素数

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit Status

方老师最近很喜欢素数，他想玩一个游戏：

现在有两个44位的素数nn和mm，你一次可以改变nn的一位数字，并且改变过后的新数字必须也是个素数，并且也不能有前导00。请问使nn变为mm最少需要多少步。

例如n=1033n=1033 m=8179m=8179

那么可行的变化是：

1033

1733

3733

3739

3779

8779

8179

Input

第一行有一个整数T(T≤100)T(T≤100)，代表测试数据的组数。

对于每组数据，每行有两个4位素数N，M（没有前导00）

Output

对于每一组数据,如果能够得到mm，输出最少的步数，否则输出Impossible

Sample input and output

Sample Input

3

1033 8179

1373 8017

1033 1033

Sample Output

6

7

0

//bfs感觉像是有点变形吧，有点难，第一次没大理解，第二次做还是没做出来

#include<stdio.h> #include<string.h> #include<math.h> #include<queue>  using namespace std; struct node{ int num; int step; }; int n,m,prime[10001],book[10001]; void pr()     //四位数的素数 { int i,flag,j; memset(prime,0,sizeof(prime)); for(i=1000;i<10000;i++) { flag=0; for(j=2;j<=sqrt(i);j++) { if(i%j==0) { flag=1; break; } } if(flag==0) prime[i]=1; } } int bfs() { int i,j,k,t[4]; memset(book,0,sizeof(book)); queue<node>Q; struct node p,q; p.num=n; p.step=0; Q.push(p); book[n]=1; while(!Q.empty()) { q=Q.front(); Q.pop(); t[0]=q.num/1000; t[1]=(q.num/100); t[2]=(q.num/10); t[3]=q.num; if(q.num==m) return q.step; for(i=0;i<4;i++) { k=t[i]; for(j=0;j<=9;j++) { if(j!=k) { t[i]=j; int f=t[0]*1000+t[1]*100+t[2]*10+t[3]; if(prime[f]==1&&book[f]==0) { book[f]=1;  p.num=f; p.step=q.step+1; Q.push(p); } } } t[i]=k; }     }     return -1;     } int main() {     int t,ans; pr(); scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); ans=bfs(); if(ans==-1) printf("Impossible\n"); else printf("%d\n",ans); } return 0; }