#include"iostream"
#include"queue"
using namespace std;
int is_prime[10000];/*prime[i]为1则说明i为素数*/
int visited[10000];
int end;/*最终要转化到的素数*/
int num[10000];//转化次数
void bfs(int i)
{
	int j,k;
    queue<int>x;
	x.push(i);
	while(x.size()!=0)
	{
		int t=x.front();//取队首元素
		visited[t]=1;
		x.pop();//出队
		if(t==end)
			return;
                       /*改变四位中的一位,即每个根结点有四个子子结点*/
		for(j=0;j<4;j++)
		{
                        char ch[5];
			sprintf(ch,"%d",t);//将整数t转化为字符串存于ch中
                            for(k=0;k<10;k++)/*改变每一位有十种可能*/
			{
                                 if(j==0&&k==0)/*最高位为0时,不能考虑,题中要求是四位数*/
			                continue;
				  int temp;
				  if(j==0)
				     temp=k*1000+(ch[1]-'0')*100+(ch[2]-'0')*10+(ch[3]-'0');
                                  else if(j==1)
			             temp=k*100+(ch[0]-'0')*1000+(ch[2]-'0')*10+(ch[3]-'0');
				  else if(j==2)
				     temp=k*10+(ch[0]-'0')*1000+(ch[1]-'0')*100+(ch[3]-'0');
				  else if(j==3)
				     temp=k+(ch[0]-'0')*1000+(ch[1]-'0')*100+(ch[2]-'0')*10;        
				  if(is_prime[temp]&&visited[temp]==0&&temp<10000)/*是素数且未被访问且在四位数之内*/
				  {
                                         num[temp]=num[t]+1;//递归求解
				          x.push(temp);//入队
				          visited[temp]=1;//标记
				  }
			}
		}
	}
}
int main()
{
	int N;
	int i,j;
	/*求10000内素数*/
	for(i=0;i<10000;i++)
		is_prime[i]=1;
	is_prime[0]=0;/*0和1不是素数*/
	is_prime[1]=0;
	for(i=2;i<10000;i++)//从2开始
		for(j=2;i*j<10000;j++)/*i*j不能越过10000*/
			is_prime[i*j]=0;
	scanf("%d",&N);
	while(N--)
	{
		int begin;
		memset(visited,0,sizeof(visited));//初始化
		memset(num,0,sizeof(num));
		scanf("%d%d",&begin,&end);
		bfs(begin);//遍历
		if(num[end]==0&&begin!=end)/*不能找到合适的*/
			printf("Impossible\n");
		else
			printf("%d\n",num[end]);
	}
	return 0;
}

• 水水更健康！ (2) jiangke 2010-08-22 08:45:51