思路：宽度优先搜索（BFS算法）
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<cstring>
using namespace std;
int a,b;
struct node{
int num;
int step;
};
node que[10000];//默认初始化为0
int visit[10000];//默认初始化为0
int prime(int d){
if(d<=1) return 0;
for(int i=2;i<=sqrt(double(d));i++)
if(d%i==0) return 0;
return 1;
}
void bfs(){
int i;
int p1,p2;
p1=0;
que[p1].num=a;
que[p1].step=0;
visit[a]=1;
p2=1;
if(a==b){//考虑 a , b 相等的时候
printf("%d\n",0);
return ;
}
while(p1<p2){
node x=que[p1];
p1++; int unit=x.num%10;//取出个位
int decade=(x.num/10)%10;//取出十位
for(i=1;i<=9;i=i+2){ //枚举个位,保证为奇数（偶数必定不是素数）
int y=(x.num/10)*10+i;
if(y==b) { //如果找到了，直接退出
printf("%d\n",x.step+1);
return ;
}
if(visit[y]==0 &&prime(y)) {
visit[y]=true;
que[p2].num=y;
que[p2].step=x.step+1;
p2++;
}
}
for(i=0;i<=9;i++){ //枚举十位
int y=(x.num/100)*100+i*10+unit;
if(y==b) { //如果找到了，直接退出
printf("%d\n",x.step+1);
return ;
}
if(visit[y]==0 &&prime(y)) {
visit[y]=true;
que[p2].num=y;
que[p2].step=x.step+1;
p2++;
}
}
for(i=0;i<=9;i++){ //枚举百位
int y=(x.num/1000)*1000+i*100+decade*10+unit;
if(y==b) { //如果找到了，直接退出
printf("%d\n",x.step+1);
return ;
}
if(visit[y]==0 &&prime(y)){
visit[y]=true;
que[p2].num=y;
que[p2].step=x.step+1;
p2++;
}
}
for(i=1;i<=9;i++) {//枚举千位，保证千位不为0
int y=i*1000+x.num%1000;
if(y==b) { //如果找到了，直接退出
printf("%d\n",x.step+1);
return ;
}
if(visit[y]==0 &&prime(y)) {
visit[y]=true;
que[p2].num=y;
que[p2].step=x.step+1;
p2++;
}
}
}
printf("Impossible\n");
return;
}
int main(){
int n;
scanf("%d",&n);
while(n--) {
memset(visit,0,sizeof(visit));//不要忘记初始化
scanf("%d%d",&a,&b);
bfs();
}
return 0;
}
下面代码优化了一下判断素数的代码
int prime(int d){
if(d==2) return 1;//特殊情况，偶数2是素数
if( d<=1 || d%2==0 ) return 0;//排除d<=1时以及d为偶数时
for(int i=3;i<=sqrt(double(d));i=i+2)
if(d%i==0) return 0;
return 1;
}