寻找两个四位素数的转变路径最短长度,构建一个素数表,然后采用广度优先搜索.本来害怕记录已经搜索过的数据会增加内存使用量,就没有设,结果广搜时队列容量超限,反而在添加了搜索记录表后大大减少内存使用量,看来有些是可以省的,而有些东西是不能省的!还有,在记录搜索过的数据时开始想,既然是四位数,那就将每个数-1000存储,可以省1000各存储单元,结果使用的时候忘记了,导致对出错的结果分析了N久才发现栽在了这里,看来有些优化是得不偿失的!
Source:
#include<iostream>
#include<queue>
using namespace std;
int search(int s);
struct Node
{
int v,s;
};
bool use[10000];
bool prim[10000];
int aim;
void GenPrim()
{
int i,j;
memset(prim,0,10000*sizeof(bool));
for(i=2;i<10000;++i)
{
if(!prim[i])
{
for(j=i+i;j<10000;j+=i)prim[j]=true;
}
}
}
int main()
{
int n,s;
GenPrim();
cin>>n;
for(;n>0;--n)
{
cin>>s>>aim;
cout<<search(s)<<endl;
}
}
int search(int s)
{
memset(use,0,10000*sizeof(bool));
int t,i;
Node c,*p=NULL;
queue<Node> q;
p=new Node();
p->v=s;
p->s=0;
while(!q.empty())q.pop();
q.push(*p);
use[s]=true;
while(!q.empty())
{
c=q.front();
q.pop();
//cout<<"["<<c.s<<","<<c.v<<"]"<<endl;
if(c.v==aim)
{
return c.s;
}
//1
t=c.v-c.v%10;
for(i=1;i<=9;i+=2)
{
if(t+i!=c.v)
{
if(!prim[t+i] && !use[t+i])
{
p=new Node();
p->v=t+i;
p->s=c.s+1;
q.push(*p);
use[t+i]=true;
}
}
}
//10
t=c.v-((c.v%100)/10)*10;
for(i=0;i<=90;i+=10)
{
if(t+i!=c.v)
{
if(!prim[t+i] && !use[t+i])
{
p=new Node();
p->v=t+i;
p->s=c.s+1;
q.push(*p);
use[t+i]=true;
}
}
}
//100
t=c.v-((c.v%1000)/100)*100;
for(i=0;i<=900;i+=100)
{
if(t+i!=c.v)
{
if(!prim[t+i] && !use[t+i])
{
p=new Node();
p->v=t+i;
p->s=c.s+1;
q.push(*p);
use[t+i]=true;
}
}
}
//1000
t=c.v%1000;
for(i=1000;i<=9000;i+=1000)
{
if(t+i!=c.v)
{
-->
- 该日志由 barak 于12年前发表在综合分类下，最后更新于 2012年09月09日.
- 转载请注明: pku3126 | 学步园 +复制链接