题目
大意：给定两个四位数的素数。每次只能改变一个数字，且改变后的数字也同样是素数，求解是否存在这样的方法。如果存在，那么最少的替换次数是多少？
例如：
1033
1733
3733
3739
3779
8779
8179
总计变化了六次，输出结果为6.
输入
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
题目分析
本题主要采用了通过欧拉筛选出四位数中所有的素数，随后利用广度优先搜索的方法对每一种变换均加以追踪枚举。
关于欧拉筛获取素数的代码解说可戳这里
此处主要分析bfs的应用。
代码
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;class num{
public:int t[5];//保存四位数的每位数字int step;//第几次变换int sum;//四位数的大小void getsum(){
sum = t[1]*1000+t[2]*100+t[3]*10+t[4];}
};int isprime[10005];//对素数标记
int prime[10005];
int cnt = 0;
void getprime(){
//欧拉筛得到10000以内的素数memset(isprime,1,sizeof(isprime));isprime[1] = 0;for(int i = 2;i<10000;++i){
if(isprime[i]) prime[++cnt]=i;for(int j = 1;j<=cnt&&(i*prime[j])<10000;++j){
isprime[i*prime[j]] = 0;if(i%prime[j]==0) break;}}
}int bfs(int init,int fin)
{
if(init == fin) return 0;num first,end;int vis[10005] = {
0};//避免重复，标记已经变换的数first.t[1] = init / 1000;first.t[2] = init/100%10;first.t[3] = (init%100)/10;first.t[4] = init%10;first.step = 0;vis[init] = 1;queue<num> qu;qu.push(first);while(!qu.empty()){
first = qu.front();qu.pop();for(int i = 1;i<5;++i){
//四个数字依次变换for(int j = 1;j<10;++j){
end = first;end.t[i] = (first.t[i]+j)%10;if(end.t[1] == 0) continue;//最高位不可为零end.getsum();if(end.sum == fin)return end.step+1;else if((isprime[end.sum]!=0)&&(vis[end.sum]!=1)){
end.step+=1;qu.push(end);vis[end.sum] = 1;}}}}return -1;
}int main()
{
int init,fin,ans,group;getprime();cin >> group;for(int i = 0;i<group;++i){
scanf("%d %d",&init,&fin);ans = bfs(init,fin);if(ans == -1) cout <<"Impossible"<<endl;else cout << ans<<endl;}return 0;
}
运行结果
