http://poj.org/problem?id=3126
题意 ： 给你两个四位数，都是素数，一个是初始素数x，一个是目标素数y，让你从x变成y，x每次只能改变1位数，来变成另外一个素数k，再改变k的一位数变成另另外一个素数，这样变下去，找到x变成y需要的最少的次数，如果无法实现，输出Impossible
思路 ： 每个数字共有4位数，每位数字有10种可能的改变值[0...9]，但最高位不允许为0，所以可以将问题转化为图：初始素数和所有经一位数值改变得到的新素数为节点，若素数a经一位改变后变为素数b，则a连向b一条边长为1的有向边<a，b>，所以若目标素数y在图中，则初始素数到目标素数的路径上的边数即为花费数目，否则无解，如此一来，就转化为x到y的最短路径了，所以使用宽度优先搜索来寻找最短路即可 BFS 。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = ;
const int maxm = ;
struct node
{
int k,step ;//当前素数为k,路径长度为step
} h[maxn] ;
int p[maxn] ;
int x,y,n,s[maxn] ;
void prim()
{
memset(p,,sizeof(p));
p[] = p[] = ;
for (int i = ; i <= maxm ; i++)
{
if(!p[i])
{
for(int j = i*i ; j <= maxm ; j += i)
{
p[j] = ;
}
}
}
}
int change(int x,int i,int j)//x的第i位数改为j
{
if(i == ) return(x/)*+j ;//个位数
else if(i == ) return (x/)*+x%+j* ;
else if(i == ) return (x/)*+x%+j* ;
else if(i == ) return (x%)+j* ;
return ;
}
int main()
{
prim() ;//生成[2....9999]之间的素数
cin>>n;//输入测试用例数
while(n--)
{
cin>>x>>y ;//输入初始素数和目标素数
h[].k = x ; //宽度优先搜索，初始素数进入队列
h[].step = ;
int l = ,r = ;//队列首尾指针初始化
memset(s,,sizeof(s)) ;//所有素数的路径长度初始化
int ans = - ;//最小花费初始化
while()
{
if(h[l].k == y)//若达到目标素数，则记下路径长度并退出循环
{
ans = h[l].step ;
break ;
}
int tk,ts ;
for(int i = ; i <= ; i++)//依次改变队首节点的每一位
{
for(int j = ; j <= ; j++)
{
if(!((j == )&&(i == )))//依次枚举第i位的改变值(不允许最高位变为0)
{
tk = change(h[l].k,i,j);//计算队首节点的第i位变为j的数tk
if(p[tk])//若tk为合数，继续枚举
continue;
ts = h[l].step+ ;//计算得到的素数tk的路径长度
if(ts >= s[tk])
continue ;//若路径长度非最短，则继续枚举
if(tk == y)//若tk为目标素数，则记下路径长度并推出循环
{
ans = ts;
break ;
}
s[tk] = ts;//记下到素数tk的路径长度
r++ ;
h[r].k = tk ;//素数tk及其路径长度入队列
h[r].step = ts ;
}
}
}
if(l == r||ans >= )//若队列空或者得到的目标素数，则退出循环
break ;
l++ ;//队首指针+1；
}
if(ans >= )//若得到目标素数，则输出最短路径
cout<<ans<<endl ;
else
cout<<"Impossible"<<endl ;
}
return ;
}