题意：简单的说就是：有一个人门牌号是一个四位数的整数，并且还是一个素数，现在他想要换成另外一个四位数且是素数的门牌号，而且，每次都只能更换这个四位数的一个位置的数 ，也就是每换一次都只改变一个数字，而且对于这个每换一个位置的数字就要花费一个单位的价格，那么，为了节约，问他从现在的这个门牌号换到想要的那个门牌号最少要多少次(也就是最少花费)
题意很明确，最少次数用bfs，菜鸟刚做搜索觉得难点在于处理每一个四位数的整数变化过程
这里我们把这个四位数的整数拆开成一个 a[4]的数组，sum就是这个数的大小，那么bfs访问过程中就是要对于sum这个整数的1~4个位置用别的数字(0~9这9个数字)看能否替换，能替换的条件包括：
1、之前没有出现过这个四位数，这里我们用flag[10][10][10][10]这个四维数组来标记，(哎哎....这里很是没有必要，浪费不少空间，不过菜鸟就只能想到这个判断方式，应该也许可以用字典树判重)
2、这个数字的某一位被替换之后形成新的数字是一个素数。。
上马：
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
struct node//当前数字的状态，用数组保存每一位，这里是四位数数字
{
int a[4];//把sum的每一位分解
int sum;// 对于每个四位数数字要素数判断，就要用到，其实sum才是这个数，
int step;//次数
}start,end;
bool flag[10][10][10][10];
bool sushu(int p)//素数判断
{
for(int i=2;i<=sqrt((double)p);i++)//这里注意把p转换为double，还有 i <= sqrt，比如对于4，如果漏掉 = 就会判断为素数
{
if(p%i==0)
return false;
}
return true;
}
//这里写得有点挫....
bool work(int i,int j,node &p)//可以用一个for进行简化
{
p.a[i]=j;
if(i==0)
{
p.sum=j*1000+p.a[1]*100+p.a[2]*10+p.a[3];
if(!sushu(p.sum) || flag[j][p.a[1]][p.a[2]][p.a[3]])
return false;
}
else if(i==1)
{
p.sum=p.a[0]*1000+j*100+p.a[2]*10+p.a[3];
if(!sushu(p.sum) || flag[p.a[0]][j][p.a[2]][p.a[3]])
return false;
}
else if(i==2)
{
p.sum=p.a[0]*1000+p.a[1]*100+j*10+p.a[3];
if(!sushu(p.sum) || flag[p.a[0]][p.a[1]][j][p.a[3]])
return false;
}
else
{
p.sum=p.a[0]*1000+p.a[1]*100+p.a[2]*10+p.a[3];
if(!sushu(p.sum) || flag[p.a[0]][p.a[1]][p.a[2]][p.a[3]])
return false;
}
flag[p.a[0]][p.a[1]][p.a[2]][p.a[3]]=true;
return true;
}
int bfs()
{
queue<node>q;
start.step=0;
q.push(start);
flag[start.a[0]][start.a[1]][start.a[2]][start.a[3]]=true;
while(!q.empty())
{
node pre=q.front();q.pop();
if(pre.a[0]==end.a[0]&&pre.a[1]==end.a[1]&&pre.a[2]==end.a[2]&&pre.a[3]==end.a[3])
return pre.step;
for(int i=0;i<4;i++)//查看pre的a[0]到a[3]
{
node pp=pre;
for(int j=0;j<=9;j++)//a[i]从0填到9
if(!(i==0&&j==0) && j!=pre.a[i] && work(i,j,pp))//对于首尾，i=0不用考虑0这种情况，那样就只有三位数啦
{
pp.step=pre.step+1;
q.push(pp);
}
}
}
return 0;
}
int main()
{
char c1[5],c2[5];
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s%s",c1,c2);//先做字符串输入
start.sum=end.sum=0;
memset(flag,false,sizeof(flag));
for(int i=0;i<4;i++)
{
start.a[i]=c1[i]-'0';//这里把字符串处理为数字数组
start.sum=start.sum*10+start.a[i];
end.a[i]=c2[i]-'0';
end.sum=end.sum*10+end.a[i];
}
printf("%d
",bfs());
}
return 0;
}
个人愚昧观点..欢迎指正和讨论