题目链接：http://poj.org/problem?id=3126
【题意】输入一个素数，求变换到指定素数所需的最小步数；（过程中也需要都是素数）
【分析】bfs；因为只有4位，所以枚举思维变换即可；先预处理一下判断是不是素数的数组f；
【代码】
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;const int maxn=1e5+10;
int f[maxn],vis[maxn];
int st,ed;
struct node{int x,step;
};void init()
{for(int i=1000;i<=9999;++i){int flag=1;for(int j=2;j*j<=i;++j)if(i%j==0){flag=0;break;}if(flag)f[i]=1;}
}
void bfs(int x)
{queue<node>q;q.push(node{x,0});while(!q.empty()){node now=q.front();q.pop();int a[4];int t=now.x;for(int i=0;i<4;++i){a[i]=t%10;t/=10;}t=1;for(int i=0;i<4;++i){for(int j=0;j<=9;++j){if(i==3 && j==0)continue;//首位不为0if(a[i]==j)continue;int tmp=now.x-a[i]*t+j*t;if(tmp==ed){printf("%d\n",now.step+1);return; }if(!vis[tmp] && f[tmp]){q.push(node{tmp,now.step+1});vis[tmp]=1;}}t*=10;}}}
int main()
{int t;scanf("%d",&t);init();while(t--){scanf("%d%d",&st,&ed);if(st==ed){puts("0");continue; }memset(vis,0,sizeof(vis));bfs(st);}
}