输入
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.样例输入
3 1033 8179 1373 8017 1033 1033样例输出
6 7 0题意大概就是首先会给出数字T(T<=100)代表样例数，然后每个样例会给你两个四位素数a,b(不含前导零，比如0123)。
每次你可以将a的一位数变为任意一个数字，但是变化之后的a1必须还是一个素数。
输出a变成b所需的最小步数，如果a无法变成b输出“Impossible”。
思路 搜索题，按照正常的BFS思路就可以解决。 但在写代码之前我们还需要先解决一下几个关键的点。
第一，我们需要在搜索之前把1000~9999中所有的素数先预处理一下，避免超时。
这里我用的是埃式筛法(当然，用欧拉筛更好，更有一种无敌的感觉[doge]) 埃式筛法
int prime[maxn]; void init() //埃式筛法 { memset(prime,0,sizeof(prime)); //全部默认是素数，标记为0 prime[1]=1; for(int i=2; i<=sqrt(maxn); i++) { if(prime[i]==0) //素数为0 { for(int j=i+i; j<=maxn; j+=i) prime[j]=1; //所有的合数标记为1 } } }想要打表的，就当没看见上面这部分吧…
其次，在BFS中的移动环节里，比如tmp=1033，对于它的每一位数，我们都需要进行改变然后将符合素数条件的数存入队列中。
但注意，后三位可以变成0~9中任意数字，第一位不能取0(前导0情况)：
//next.x代表变化之后的数 //now.x代表当前数字 for(int j=0; j<4; j++) //j=0:处理个位 j=1:处理十位 j=2:处理百位 j=3:处理千位 { for(int i=0; i<=9; i++) { if(j==0)//个位 { next.x=now.x-now.x%10+i; } else if(j==1)//十位 { next.x=now.x+(i-now.x%100/10)*10; } else if(j==2)//百位 { next.x=now.x+(i-now.x%1000/100)*100; } else if(j==3&&i!=0)//千位，千位不能为0 { next.x=now.x+(i-now.x/1000)*1000; //这几个公式如果不理解可以自己手动算一下，比较简单 } if(prime[next.x]==0&&!vis[next.x]) //判断改变后的数是否是素数并且之前从未用过 { q.push(next); vis[next.x]=true; } } }最后，就是整理一下出代码了，「伊丽莎白」！ 代码
#define _CRT_SBCURE_NO_DEPRECATE #include <set> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #include <functional> using namespace std; int n,a,b; //n:样例数 int prime[10004]; //这里我是直接搬的模板，将10000之内的数全部处理了 bool vis[10004]; struct node { int x; int step; }; void init() //埃式筛法 { prime[1]=1; for(int i=2; i<=sqrt(10000); i++) { if(prime[i]==0) { for(int j=i+i; j<=10000; j+=i) prime[j]=1; } } } void bfs() { node now,next; queue<node>q; now.x=a; now.step=0; q.push(now); vis[a]=true; while(!q.empty()) { now=q.front(); q.pop(); next.step=now.step+1; //无论如何操作，步数都+1 if(now.x==b) { printf("%d\n",now.step); return ; } for(int j=0; j<4; j++) //j=0:处理个位 j=1:处理十位 j=2:处理百位 j=3:处理千位 { for(int i=0; i<=9; i++) { if(j==0)//个位 { next.x=now.x-now.x%10+i; } else if(j==1)//十位 { next.x=now.x+(i-now.x%100/10)*10; } else if(j==2)//百位 { next.x=now.x+(i-now.x%1000/100)*100; } else if(j==3&&i!=0)//千位，千位不能为0 { next.x=now.x+(i-now.x/1000)*1000; //这几个公式如果不理解可以自己手动算一下，比较简单 } if(prime[next.x]==0&&!vis[next.x]) { q.push(next); vis[next.x]=true; } } } } printf("Impossible\n"); return; } int main() { memset(prime,0,sizeof(prime)); //全部初始化为0 init(); //预处理素数 scanf("%d",&n); while(n--) { memset(vis,false,sizeof(vis)); scanf("%d%d",&a,&b); if(a==b) //特判一下相等的时候 printf("0\n"); else bfs(); } return 0; }记住我们的宗旨:一条路走到黑！ “吾心吾行，澄如明镜；所作所为，皆属正义。”
溜了溜了~
