筛个素数表+BFS
貌似数据里没有impossible的情况
#include<iostream>
using namespace std;
#define M 10000
bool prime[M];
bool visit[M];
int s,e;
int step;
void crearprimetable()//筛素数表
{
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;
}
void bfs()
{
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)
{
step++;
trear=rear;
while(front<trear)
{
num=que[front++];
for(i=1;i<10;i++)//换个位
{
t=num/10*10+i;
if(!prime[t] && !visit[t])
if(t==e) return ;
else {que[rear++]=t;visit[t]=true;}
}
for(i=0;i<10;i++)//换十位
{
t=num/100*100+i*10+num%10;
if(!prime[t] && !visit[t])
if(t==e) return ;
else {que[rear++]=t;visit[t]=true;}
}
for(i=0;i<10;i++)//换百位
{
t=num/1000*1000+i*100+num%100;
if(!prime[t] && !visit[t])
if(t==e) return ;
else {que[rear++]=t;visit[t]=true;}
}
for(i=1;i<10;i++)//换百位
{
t=i*1000+num%1000;
if(!prime[t] && !visit[t])
if(t==e) return ;
else {que[rear++]=t;visit[t]=true;}
}
}
}
}
int main()
{
int n;
crearprimetable();
scanf("%d",&n);
while(n--)
{
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 阅读(170)
评论(0) 编辑 收藏 引用 所属分类:
POJ