#include<iostream>
#include<fstream>
#include<queue>
#include<cmath>
using namespace std;

int a[9999];

bool is_prime(int a)
{
	double b = a;
	for(int i=2; i<sqrt(b); i++)
	{
		if(a%i==0)
		{
			return false;
		}
	}
	return true;
}
bool solve(char *s, char *e)
{
	queue<char *> q;
	q.push(s);
	int si = (s[0]-'0')*1000+(s[1]-'0')*100+(s[2]-'0')*10+(s[3]-'0');//atoi(s);
	int ei = (e[0]-'0')*1000+(e[1]-'0')*100+(e[2]-'0')*10+(e[3]-'0');//atoi(e);
	while(!q.empty())
	{
		char *f = q.front();
		q.pop();
		int fi = (f[0]-'0')*1000+(f[1]-'0')*100+(f[2]-'0')*10+(f[3]-'0');//atoi(f);
		char t[5];
		strcpy(t, f);
		int i = 0;
		for(; i<4; i++)
		{
			int j=0;
			for(; j<10; j++)
			{
				if(j==f[i]-'0' || (j==0 && i==0))
				{
					continue;
				}
				t[i] = j+'0';
				int m = (t[0]-'0')*1000+(t[1]-'0')*100+(t[2]-'0')*10+(t[3]-'0');//atoi(t);
				if(m == si)
				{
					continue;
				}
				if(m == ei && (a[ei]>a[fi]+1 || a[ei]==0))
				{
					a[ei]=a[fi]+1;
					break;
				}
				else if(is_prime(m) && ((a[m]==0||a[m]>a[fi]+1) && (a[ei]==0||a[ei]>a[fi]+1)))
				{
					char *tmp = new char[5];
					strcpy(tmp, t);
					q.push(tmp);
					a[m] = a[fi]+1;
				}
			}
			if(j<10)
			{
				break;
			}
			t[i] = f[i];
		}
		delete f;
	}
	return false;
}
int main()
{
	int c=0;
	/*fstream in;
	in.open("test.txt");*/
	cin>>c;//
	int i=0;
	for(; i<c; i++)
	{
		char *s = new char[5];
		char *e = new char[5];
		cin>>s>>e;//
		if(strcmp(s, e)==0)
		{
			cout<<0<<endl;
			continue;
		}
		memset(a, 0, sizeof(int)*10000);//memset(a, 0, sizeof(int)*9999);
		solve(s,e);
		int ei = (e[0]-'0')*1000+(e[1]-'0')*100+(e[2]-'0')*10+(e[3]-'0');//atoi(e);
		if(a[ei]>0)
			cout<<a[ei]<<endl;
		else
			cout<<"Impossible"<<endl;
		//delete s;
		delete e;
	}
	return 0;
}

• Re:大牛请看代码,为什么WA (43) liushijian 2010-01-04 20:12:19
  • Re:大牛请看代码,为什么WA (61) liushijian 2010-01-04 20:14:24
    • Re:大牛请看代码,为什么WA (25) linbzh 2010-01-09 16:59:24