本文共 1386 字，大约阅读时间需要 4 分钟。
这道题是道广搜题，因为爬虫等写过，所以队列还比较清楚，基本上就是一个set保存已访问过的（域名或这里的素数）还有一个队列保存要访问的内容。
我这里的做法是两个队列，一个队列cur保存现在正在处理的素数，另一个队列next保存处理过程中出现的新素数，也就是多一次变换之后的素数。
处理或者说变换的过程就是把每位（1~4位）从0~9都试一遍（不能和原来的数相同，且最高位不能变成0即可）。这样一直从源素数变为目标素数为止。
感觉AC了之后看代码改进代码的动力就不足了。。。一个比较容易想到的改进方法是用素数筛选法把4位数的素数筛选出来，这样也不必每算一个数都进行一次判断了。
我这个代码的memory308k，时间204ms。别人的时间都很短（我的1/10）。
代码如下：
#include#include #include #include #include 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 visited; queue cur; cur.push(p1); visited.insert(p1); while(true) { queue 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<
转载地址：http://pxxli.baihongyu.com/