学步园

这道题是道广搜题，因为爬虫等写过，所以队列还比较清楚，基本上就是一个set保存已访问过的（域名或这里的素数）还有一个队列保存要访问的内容。

我这里的做法是两个队列，一个队列cur保存现在正在处理的素数，另一个队列next保存处理过程中出现的新素数，也就是多一次变换之后的素数。

处理或者说变换的过程就是把每位（1~4位）从0~9都试一遍（不能和原来的数相同，且最高位不能变成0即可）。这样一直从源素数变为目标素数为止。

感觉AC了之后看代码改进代码的动力就不足了。。。一个比较容易想到的改进方法是用素数筛选法把4位数的素数筛选出来，这样也不必每算一个数都进行一次判断了。

我这个代码的memory308k，时间204ms。别人的时间都很短（我的1/10）。

代码如下：

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <cmath>

using namespace std;

bool isprime(int n)
{
	for(int i = 2; i <= sqrt(double(n)); ++i)
	{
		if(n % i == 0)
		{
			return false;
		}
	}
	return true;
}

int primetoprime(int p1, int p2, int nb)
{
	int step = 0;
	set<int> visited;
	queue<int> cur;
	cur.push(p1);
	visited.insert(p1);
	while(true)
	{
		queue<int> next;
		while(!cur.empty())
		{
			int p = cur.front();
			cur.pop();
			if(p == p2)
				return step;
			int base = 1;
			for(int i = 0; i < nb; ++i)
			{
				int bit = (p / base) % 10;
				for(int j = 0; j <= 9; ++j)
				{
					if(i == nb - 1 && j == 0)//the most significant bit cannot be zero
						continue;
					int tmp = p;
					if(j == bit)
						continue;
					tmp = tmp + (j - bit) * base;
					if(isprime(tmp) && visited.find(tmp) == visited.end())
					{
						next.push(tmp);
						visited.insert(tmp);
					}
				}
				base *= 10;
			}
		}
		step++;
		cur = next;
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i = 0; i < n; ++i)
	{	
		int p1, p2;
		cin>>p1>>p2;
		/*
		int nb = 1;
		int tmp = p1;
		while(tmp > 0)
		{
			tmp /= 10;
			nb++;
		}
		*/
		cout<<primetoprime(p1, p2, 4)<<endl;
	}
	return 0;
}