http://poj.org/problem?

id=3126

题目大意：

给你两个四位的素数s和t，要求每次改变一个数字。使得改变后的数字也为素数，求s变化到t的最少变化次数。

思路：

首先求出全部4位素数。

对于两个素数之间，假设仅仅相差一个数字，那么就建立图。（双向）

最后求最短路就可以（能够SPFA也能够BFS）

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

using namespace std;

const int MAXN=10000+10;

const int INF=0x3ffffff;

bool isprimer[MAXN];

int primer[MAXN],num;

int head[MAXN],len;

struct edge

{

	int to,next;

}e[MAXN*10];

void add(int from,int to)

{

	e[len].to=to;

	e[len].next=head[from];

	head[from]=len++;

}

//推断两个数仅有一个数字不同

bool judge(char *x,char *y)

{

	int cnt=0;

	for(int i=0;i<4;i++)

		if(x[i]==y[i])

		  cnt++;

	return cnt==3;

}

int dis[MAXN];

bool vis[MAXN];

int spfa(int s,int t)

{

		for(int i=1000;i<=10000;i++)

		{

			dis[i]=INF;

			vis[i]=0;

		}

		dis[s]=0;

		vis[s]=true;

		queue<int> q;

		q.push(s);

		while(!q.empty())

		{

			int cur=q.front();

			q.pop();

			for(int i=head[cur];i!=-1;i=e[i].next)

			{

				int to=e[i].to;

				if(dis[cur]+ 1 < dis[to])

				{

					dis[to]=dis[cur]+1;

					if(!vis[to])

						q.push(to);

				}

			}

		}

		return dis[t];

}

int main()

{

	memset(head,-1,sizeof(head));

	num=len=0;

	for(int i=2;i*i<MAXN;i++)

	{

		if(!isprimer[i])

			for(int j=i;j*i<MAXN;j++)

				isprimer[i*j]=true;

	}

	for(int i=1000;i<10000;i++)

		if(!isprimer[i])

				primer[num++]=i;

	//printf("%d\n",num);

	char cur[5],temp[5];

	for(int i=0;i<num;i++)

	{

		sprintf(cur,"%d",primer[i]);

	//	printf("%s\n",cur);

		for(int j=i+1;j<num;j++)

		{

			sprintf(temp,"%d",primer[j]);

			if(judge(cur,temp))

			{

				add(primer[j],primer[i]);

				add(primer[i],primer[j]);

			}

		}

	}

	int T;

	scanf("%d",&T);

	while(T--)

	{

		int a,b;

		scanf("%d%d",&a,&b);

		if(isprimer[b])

		{

			printf("Impossible\n");

			continue;

		}

		int ans=spfa(a,b);

		if(ans==INF)

			printf("Impossible\n");

		else

			printf("%d\n",ans);

	}

	return 0;

}