POJ - 3126 Prime Path解题报告

给你两个四位数a,b。每次可以给a的一位更换一个数，要求更换之后得到的数必须是质数，问你最少几次更换，就可以使得a变成b。测试数据100组。

#include<iostream>#include<queue>#include<string.h>#include<math.h>#include<stdio.h>#define N 10000using namespace std;struct number{	int num;	int a[4];};int n;bool vis[N]={0};int dis[N]={0};queue<number>q;bool is_PRime(int x){	if(x==0)return 0;	for(int i=2;i<=sqrt(x);i++)	{		if(x%i==0)return 0;	}	return 1;}void bfs(int s,int e){		number t;	t.num=s;	for(int i=0;i<4;i++)	{		t.a[i]=s%10;		s=s/10;	}	vis[t.num]=1;	q.push(t);	int flag=0;	while(!q.empty())	{		for(int i=0;i<4;i++)//扩展 		{			for(int j=0;j<=9;j++)			{				number l;				l=q.front();				l.a[i]=j;				l.num=l.a[0]+l.a[1]*10+l.a[2]*100+l.a[3]*1000;				if(vis[l.num]==1)continue;				if(l.num<1000)continue;				if(!is_prime(l.num))continue;				dis[l.num]=dis[q.front().num]+1;				//cout<<l.a[3]<<l.a[2]<<l.a[1]<<l.a[0]<<"  "<<dis[l.num]<<endl;				if(l.num==e)				{					flag=1;break;				}				vis[l.num]=1;				q.push(l);			}			if(flag==1)break;		}		if(flag==1)break;		q.pop();	}}int main(){	cin>>n;	for(int i=0;i<n;i++)	{		int s,e;		scanf("%d %d",&s,&e);		bfs(s,e);		printf("%d/n",dis[e]);		memset(vis,0,sizeof(vis));		memset(dis,0,sizeof(dis));		while(!q.empty())		{			q.pop();		}	}	}
有一个要求是，这些数没有前导零，我一直没读懂，然后样例过不去想了半天才知道是说，这些四位数都是四位数，既必须大于等于1000。