筛个素数表+BFS
貌似数据里没有impossible的情况
#include<iostream>
using namespace std;
#define M 10000
bool prime[M];
bool visit[M];
int s,e;
int step;
void crearprimetable()//筛素数表
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j;
//prime[0]=prime[1]=1;
for(i=2;i<M;i++) //判断i是不是素数
if(prime[i]==0) //是
for(j=i+i;j<M;j+=i) //把是i倍数的数j记上1,不是素数.
prime[j]=1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void bfs()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j,k,num,t;
int que[10000];
int front,rear,trear;
step=0;
if(s==e) return ;
front=rear=0;
que[rear++]=s;
while(front<rear)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
step++;
trear=rear;
while(front<trear)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
num=que[front++];
for(i=1;i<10;i++)//换个位
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
t=num/10*10+i;
if(!prime[t] && !visit[t])
if(t==e) return ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{que[rear++]=t;visit[t]=true;}
}
for(i=0;i<10;i++)//换十位
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
t=num/100*100+i*10+num%10;
if(!prime[t] && !visit[t])
if(t==e) return ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{que[rear++]=t;visit[t]=true;}
}
for(i=0;i<10;i++)//换百位
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
t=num/1000*1000+i*100+num%100;
if(!prime[t] && !visit[t])
if(t==e) return ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{que[rear++]=t;visit[t]=true;}
}
for(i=1;i<10;i++)//换百位
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
t=i*1000+num%1000;
if(!prime[t] && !visit[t])
if(t==e) return ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{que[rear++]=t;visit[t]=true;}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int n;
crearprimetable();
scanf("%d",&n);
while(n--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d%d",&s,&e);
memset(visit,0,sizeof(visit));
bfs();
printf("%d\n",step);
}
return 0;
}
posted on 2009-07-23 16:27
wyiu 阅读(163)
评论(0) 编辑 收藏 引用 所属分类:
POJ