记录编号	42938	评测结果	TAAAAAAAAA
题目名称	[省常中] 素数路	最终得分	90
用户昵称	Cloud	是否通过	未通过
代码语言	C++	运行时间	1.647 s
提交时间	2012-10-02 21:04:42	内存使用	0.31 MiB

#include<fstream>
#include<set>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
set<int> s;
set<int> a;
struct yu
{
	int num[4];
	int m;
};
queue<yu> dq;
yu tmp;
int main(void)
{
	ifstream fin("primepath.in");
	ofstream fout("primepath.out");
	int n;
	int i,j,k;
	for(n=1000;n<9999;n++)
	{
		bool f=1;
		for(i=2;i<=pow((double)n,0.5);i++)
			if(n%i==0)
			{
				f=0;
				break;
			}
		if(f)
			s.insert(n);
	}
	string begin;
	int end;
	fin>>begin;
	fin>>end;
	for(i=0;i<4;i++)
		tmp.num[i]=begin[i]-'0';
	dq.push(tmp);
	while(dq.size())
	{
		for(i=0;i<4;i++)
		{
			for(j=0;j<10;j++)
			{
				tmp=dq.front();
				if(j==tmp.num[i])
					continue;
				tmp.num[i]=j;
				n=0;
				for(k=3;k>-1;k--)
					n+=tmp.num[3-k]*pow((double)10,(double)k);
				if(s.find(n)!=s.end()&&a.find(n)==a.end())
				{
					tmp.m++;
					dq.push(tmp);
					s.insert(n);
					if(n==end)
					{
						fout<<tmp.m;
						return 0;
					}
				}
			}
		}
		dq.pop();
	}
	fout<<"Impossible";
	fin.close();
	fout.close();
	return 0;
}