篩個(gè)素?cái)?shù)表+BFS
貌似數(shù)據(jù)里沒(méi)有impossible的情況
#include<iostream>
using namespace std;
#define M 10000
bool prime[M];
bool visit[M];
int s,e;
int step;
void crearprimetable()//篩素?cái)?shù)表
{
int i,j;
//prime[0]=prime[1]=1;
for(i=2;i<M;i++) //判斷i是不是素?cái)?shù)
if(prime[i]==0) //是
for(j=i+i;j<M;j+=i) //把是i倍數(shù)的數(shù)j記上1,不是素?cái)?shù).
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++)//換個(gè)位
{
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 閱讀(178)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ