題意：給你兩個四位的素數，從 n - > m 要變換幾回...
思路：素數打表 + 廣搜，因為好久沒寫搜索了，所以卡了好久才1過了，
用一般的對列，再用一個數組記錄它的步數，就OK了..
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define manx 25000
int n,m,pos[manx],mark[manx],flag;
bool s[manx];
void prime(){
memset(s,0,sizeof(s));
for(int i=2;i*i<manx;i++){
if(!s[i]){
for(int j=2;j*i<manx;j++){
s[i*j]=1;
}
}
}
}
void bfs(){
memset(pos,0,sizeof(pos));
memset(mark,0,sizeof(mark));
queue<int>que;
while(!que.empty()) que.pop();
que.push(n);
mark[n]=1;
while(!que.empty()){
if(que.front()==m) {
flag=1;
printf("%d\n",pos[m]);
break;
}
int temp=que.front();
que.pop();
for(int i=0;i<=9;i++){
if(!s[temp/10*10+i] && !mark[temp/10*10+i]){ /// 處理個位
mark[temp/10*10+i]=1;
que.push(temp/10*10+i);
pos[temp/10*10+i]=pos[temp]+1;
}
if(!s[temp/100*100+temp%10+i*10] && !mark[temp/100*100+temp%10+i*10]) { /// 處理十位
mark[temp/100*100+temp%10+i*10]=1;
que.push(temp/100*100+temp%10+i*10);
pos[temp/100*100+temp%10+i*10]=pos[temp]+1;
}
if(!s[temp/1000*1000+temp%100+i*100] && !mark[temp/1000*1000+temp%100+i*100]) { /// 處理百位
mark[temp/1000*1000+temp%100+i*100]=1;
que.push(temp/1000*1000+temp%100+i*100);
pos[temp/1000*1000+temp%100+i*100]=pos[temp]+1;
}
if(!s[temp%1000+i*1000] && !mark[temp%1000+i*1000] && temp%1000+i*1000>=1000){ /// 處理千位
mark[temp%1000+i*1000]=1;
que.push(temp%1000+i*1000);
pos[temp%1000+i*1000]=pos[temp]+1;
}
}
}
}
int main(){
prime();
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
flag=0;
bfs();
if(!flag) printf("Impossible\n");
}
}
