POJ 3126 Prime Path (BFS) （F）

题意：给出两个数  求左边的数变到右边的数需要几步

变得方法是: 从一个四位数变成另一个四位数，每次只能变其中的一位数，且每次变的数都是质数(题目给出的两数均为质数)

思路：

在输入之前  先用数组将1-10000内的质数全部进行标记

枚举  从第一位到第四位  每位的数字从0到9，一一检验是否为质数  是的话  他的步数为前者+1，同时标记已经被访问过了

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define maxn 10010
bool prime[maxn];//判断是否为质数
int isprime[maxn];//记录质数
int tot;
void findprime(int n)//对前n个数  高效质数打表
{
	memset(prime,false,sizeof prime);
	prime[1]=true;
	for(int i=2;i<=n;i++)
	{
		if(!prime[i])
		{
			tot++;
			isprime[tot]=i;
		}
		for(int  j=1;(j<=tot&&i*isprime[j]<=n);j++)
		{
			prime[i*isprime[j]]=true;
			if(i%isprime[j]==0)break;//点睛之笔
		}
	}
}

int n,m;
int step[maxn];//记录步数
bool vis[maxn];//记录这个数有没有判断过
int change(int i,int j,int s)
{
	if(i==1)
	{
		return s/10*10+j;
	}
	else if(i==2)
	{
		return s%10+s/100*100+j*10;
	}
	else if(i==3)
	{
		return s%100+s/1000*1000+j*100;
	}
	else
		return s%1000+j*1000;
}
void bfs()
{
	queue<int>q;
	q.push(n);
	step[n]=0;
	vis[n]=true;
	while(!q.empty())
	{
		int p=q.front();
		q.pop();
		if(p==m)
		{
			printf("%d\n",step[m]);
			return ;
		}
		for(int i=1;i<=4;i++)
		{
			for(int j=0;j<=9;j++)
			{
				int x=change(i,j,p);
				if(x>1000&&x<=9999&&!prime[x]&&!vis[x])
				{
					q.push(x);
					vis[x]=true;
					step[x]=step[p]+1;
				}
			}
		}
	}
}
int main()
{
	findprime(10000);
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(vis,0,sizeof vis);
		memset(step,0,sizeof step);
		scanf("%d%d",&n,&m);
		bfs();
	}
    return 0;
}