记录编号	224673	评测结果	AAAAAAAAAA
题目名称	[省常中] 素数路	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2016-02-16 15:41:53	内存使用	0.37 MiB

#include<cstdio>
#include<queue>
using namespace std; 
bool not_prime[10005];
bool prime[10][10][10][10];
bool able[10][10][10][10];
int step[10][10][10][10];
struct num{
	int a,b,c,d;
	num(int A,int B,int C,int D){
		a=A;b=B;c=C;d=D;
	}
};
queue<num> q;
int main(){
	freopen("primepath.in","r",stdin);
	freopen("primepath.out","w",stdout);
	for(int i = 2;i<101;++i){
		if(!not_prime[i]){
			for(int j = i*i;j<10005;j+=i)not_prime[j]=true;
		}
	}
	for(int i = 1000;i<10000;++i){
		if(!not_prime[i]){
			prime[i/1000][i/100%10][i/10%10][i%10]=true;
		}
	}
	int n,m;
	scanf("%d %d",&n,&m);
	able[n/1000][n/100%10][n/10%10][n%10]=true;
	q.push(num(n/1000,n/100%10,n/10%10,n%10));
	while(!q.empty()){
		num tmp=q.front();
		for(int i = 1;i<=9;++i){
			if(q.front().a!=i){
				tmp.a=i;
				if(prime[tmp.a][tmp.b][tmp.c][tmp.d]){
					if(!able[tmp.a][tmp.b][tmp.c][tmp.d]){
						able[tmp.a][tmp.b][tmp.c][tmp.d]=true;
						step[tmp.a][tmp.b][tmp.c][tmp.d]=step[q.front().a][tmp.b][tmp.c][tmp.d]+1;
						q.push(num(tmp.a,tmp.b,tmp.c,tmp.d));
					}
				}
			}
		}
		tmp = q.front();
		for(int i = 0;i<=9;++i){
			if(q.front().b!=i){
				tmp.b=i;
				if(prime[tmp.a][tmp.b][tmp.c][tmp.d]){
					if(!able[tmp.a][tmp.b][tmp.c][tmp.d]){
						able[tmp.a][tmp.b][tmp.c][tmp.d]=true;
						step[tmp.a][tmp.b][tmp.c][tmp.d]=step[tmp.a][q.front().b][tmp.c][tmp.d]+1;
						q.push(num(tmp.a,tmp.b,tmp.c,tmp.d));
					}
				}
			}
		}
		tmp=q.front();
		for(int i = 0;i<=9;++i){
			if(q.front().c!=i){
				tmp.c=i;
				if(prime[tmp.a][tmp.b][tmp.c][tmp.d]){
					if(!able[tmp.a][tmp.b][tmp.c][tmp.d]){
						able[tmp.a][tmp.b][tmp.c][tmp.d]=true;
						step[tmp.a][tmp.b][tmp.c][tmp.d]=step[tmp.a][tmp.b][q.front().c][tmp.d]+1;
						q.push(num(tmp.a,tmp.b,tmp.c,tmp.d));
					}
				}
			}
		}
		tmp=q.front();
		for(int i = 0;i<=9;++i){
			if(q.front().d!=i){
				tmp.d=i;
				if(prime[tmp.a][tmp.b][tmp.c][tmp.d]){
					if(!able[tmp.a][tmp.b][tmp.c][tmp.d]){
						able[tmp.a][tmp.b][tmp.c][tmp.d]=true;
						step[tmp.a][tmp.b][tmp.c][tmp.d]=step[tmp.a][tmp.b][tmp.c][q.front().d]+1;
						q.push(num(tmp.a,tmp.b,tmp.c,tmp.d));
					}
				}
			}
		}
		q.pop();
	}
	if(able[m/1000][m/100%10][m/10%10][m%10])printf("%d\n",step[m/1000][m/100%10][m/10%10][m%10]);
	else printf("Impossible\n");
	fclose(stdin);fclose(stdout);
	return 0;
}