POJ 3126 素数+广搜
题意：给你两个四位的素数，从 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");
}
}
补充：软件开发 , C++ ,
