题意：给出两个四位数的素数，按如下规则变换，使得将第一位数变换成第二位数的花费最少，输出最少值，否则输出0。
每次只能变换四位数的其中一位数，使得变换后的数也为素数，每次变换都需要1英镑(即使换上的数是以前被换下的)。
思路：若素数a可以按上述规则转化为b，则可以看做a、b直接有一条边。显然，从初始值到目标值的路径上的边数即为花费的
数目，这样一来，就相当于求最短路径。由于题目只要求最小花费数，所以不需要存储有向图。
用BFS搜索，每次枚举当前值x所能变换得到的值y，若y满足条件，将y以及从初始值达到当前y值所需要的次数压入队列。
只要当从队列取出的数值等于目标值，此时的花费即为答案，结束循环。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue> using namespace std; int start,goal,t;//start:初始值，goal:目标值
int prime[];
int vis[];//标记数i是否之前已经被转换过 struct Node{
int num;
int step; //从start变为num所需要的步数
}; //将x的第i位的值改成j
int change(int x,int i,int j){
if(i==)
return x-x%+j;
if(i==)
return (x/)*+x%+j*;
if(i==)
return (x/)*+x%+j*;
if(i==)
return x%+j*;
return ;
} int bfs(int start,int ends){
queue<Node> q;
Node a,b;
vis[start]=;
a.num=start;
a.step=;
q.push(a);
while(!q.empty()){
a=q.front();
q.pop();
//只要a.num等于目标值的话，就退出循环。
//因为不可能有比这花费最少的情况了。
if(a.num==ends){
return a.step;
}
vis[a.num]=;
//枚举
for(int i=;i<=;i++){
for(int j=;j<=;j++){
//若为偶数，直接继续
if(i== && j%==)
continue;
if(i==&&j==)
continue;
int temp=change(a.num,i,j);
if(prime[temp]== || vis[temp])
continue;
b.num=temp;
b.step=a.step+;
q.push(b);
}
} }
return -;
}
//预处理1000~9999的素数
void dealWithPrime(){
memset(prime,,sizeof(prime));
for(int i=;i<;i++){
if(prime[i]){
for(int j=i*i;j<;j+=i){
prime[j]=;
}
}
}
} int main()
{
dealWithPrime();
scanf("%d",&t);
for(int i=;i<=t;i++){
scanf("%d%d",&start,&goal);
memset(vis,,sizeof(vis));
int ans=bfs(start,goal);
if(ans==-)
printf("0\n");
else
printf("%d\n",ans);
}
return ;
}