Prime Path POJ - 3126
题目描述：给出一个素数，要求通过变换这个素数的某个数字，使变换后的数字仍然是素数，要求变换到给定的一个素数停止，求最少的变化次数。
解题分析：bfs模拟求最短路就行。把每个数当做图中的一个点。
代码入下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
const int maxn=10000+10;
const int INF=0x3f3f3f3f;
int prime[maxn],dist[maxn];
bool bfs(int st,int ed)
{
queue< int > q;
q.push(st);
while(!q.empty())
{
int temp=q.front();
q.pop();
if(temp==ed)
{
dist[ed]=dist[temp];
return true;
}
int a=temp/1000,b=temp%1000/100,c=temp%100/10,d=temp%10;
int num;
for(int i=0;i<4;i++)//下面枚举可能的路径
{
for(int j=0;j<=9;j++)
{
if(i==0) num=j*1000+b*100+c*10+d;
else if(i==1) num=a*1000+100*j+c*10+d;
else if(i==2) num=a*1000+b*100+j*10+d;
else if(i==3) num=a*1000+b*100+c*10+j;
if(num>=1000&&num<9999&&!prime[num]&&dist[num]==INF)
{
dist[num]=dist[temp]+1;
q.push(num);
}
}
}
}
return false;
}
int main()
{
memset(prime,0,sizeof(prime));
int k=sqrt(10000+0.5);
for(int i=2;i<=k;i++)//素数打表
{
if(!prime[i])
{
for(int j=i*i;j<=10000;j+=i)
prime[j]=1;
}
}
int kase;
scanf("%d",&kase);
while(kase--)
{
int st,ed;
scanf("%d %d",&st,&ed);
memset(dist,0x3f,sizeof(dist));
dist[st]=0;
if(bfs(st,ed)) printf("%d\n",dist[ed]);
else printf("Impossible\n");
}
return 0;
}
