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 10000
using 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。