【POJ|POJ - 3126（Bfs)】题目分类：简单搜索
题目链接：https://vjudge.net/contest/65959#problem/F
题目大意：
给出两个四位数的奇数，设前者为数A,后者为B,要求是数A每次只能变化一个数字，且变化出的四位数必须是奇数，求变化到B所需的最小次数。
数据规模：
T<100;
解题思路：
Bfs
代码如下：
">#include
#include
#include
#include
using namespace std;
const int maxn=1e4+10;
int a,b;
int vis[maxn];
int pp[4]={1,10,100,1000};
bool ok(int x,int nw){
if(x<1000)return false;
if(vis[x]<=vis[nw]+1)return false;
for(int i=2;
i<=sqrt(x);
i++){
if(x%i==0)return false;
}
return true;
}
int bfs(){
queueQ;
Q.push(a);
vis[a]=0;
int nw,nxt;
while(!Q.empty()){
nw=Q.front();
if(nw==b)return vis[nw];
Q.pop();
for(int i=0;
i<4;
i++){
int sum=nw/pp[i]/10*pp[i]*10+nw%pp[i];
for(int j=0;
j<10;
j++){
int sum2=sum+j*pp[i];
if(ok(sum2,nw)){
Q.push(sum2);
vis[sum2]=vis[nw]+1;
}
}
}
}
return -1;
}int main(){
int t;
scanf("%d",&t);
while(t--){
fill(vis,vis+maxn,0x3fffffff);
scanf("%d%d",&a,&b);
printf("%d\n",bfs());
}
return 0;
} 
