poj 3126 BFS+素数筛

题意：
给两个四位数，均为质数。要求从第一个四位数每次改变其中的一个数字最终得到第二个四位数。改变过程中，必须保证所得四位数为质数。求出 最少需要改变几次。

#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;
const int maxn=9999+10;
int prime[maxn];
bool vis[maxn];
struct node{
	int x,time;
}; 
node start,ed;
bool is_prime(int x)
{
	for(int i=2;i<=sqrt(x);i++)
	{
		if(x%i==0)
		return false;
	}
	return true;
}
void init()//初始化判断是否为质数 
{
	for(int i=1000;i<=maxn;i++)
		prime[i]=i;
	for(int i=1000;i<=maxn;i++)
	{
		if(is_prime(prime[i]))
			prime[i]=1;//质数 
			else
			prime[i]=0;//不为质数 
	}
}
int bfs()
{
	queue<node>q;
	node cur,ne;
	q.push(start);
	while(!q.empty())
	{
		cur=q.front();
		q.pop();
		if(cur.x==ed.x)
			return cur.time;
			for(int i=1;i<=9;i=i+2)//对个位处理 
			{
				ne.x=cur.x/10*10+i;
				if(ne.x==cur.x)
				continue;
				if(prime[ne.x]&&!vis[ne.x])
				{
					vis[ne.x]=1;
					ne.time=cur.time+1;
					q.push(ne);
				}
			}
			for(int i=0;i<=9;i++)//对十位处理 
			{
				ne.x=cur.x/100*100+i*10+cur.x%10;
				if(ne.x==cur.x)
				continue;
				if(prime[ne.x]&&!vis[ne.x])
				{
					vis[ne.x]=1;
					ne.time=cur.time+1;
					q.push(ne);
				}
			}
			for(int i=0;i<=9;i++)//对百位处理 
			{
				ne.x=cur.x/1000*1000+i*100+cur.x%100;
				if(ne.x==cur.x)
				continue;
				if(prime[ne.x]&&!vis[ne.x])
				{
					vis[ne.x]=1;
					ne.time=cur.time+1;
					q.push(ne);
				}
			}
			for(int i=1;i<=9;i++)
			{
				ne.x=i*1000+cur.x%1000;
				if(ne.x==cur.x)
				continue;
				if(prime[ne.x]&&!vis[ne.x])
				{
					vis[ne.x]=1;
					ne.time=cur.time+1;
					q.push(ne);
				}
			}
	}
	return -1;
}
int main()
{
	memset(prime,0,sizeof(prime));
	
	int t;
	scanf("%d",&t);
	init();
	while(t--)
	{
		memset(vis,false,sizeof(vis));
		scanf("%d%d",&start.x,&ed.x);
		start.time=0;
		int ans=bfs();
		if(ans!=-1)
		printf("%d\n",ans);
		else
		printf("Impossible\n");
	 } 
	 return 0;
}