pku 3126給出兩個4位素數(shù)a,b，每次a變一個位上的數(shù)字，問如何變使得變成b的步驟最少。
先打素數(shù)表，然后在兩個素數(shù)之間，若只差一個數(shù)字，則連一條邊。最后只需從a寬搜到b即可。
// 搜索
#include <iostream>
#include <math.h>
using namespace std;
int p[1300];
bool G[1300][1300],d[1300];
int cnt;
int target;
void prim()
{
//memset(p,0,sizeof(p));
cnt=0;
int i;
for(i=1000;i<10000;i++)
{
int up=(int)sqrt(i),flag=0;
for(int j=2;j<=up;j++)
{
if(i%j==0) {flag=1;break;}
}
if(flag==0) {p[cnt++]=i;}
}
//printf("%d\n",cnt);
//for(i=0;i<cnt;i++) printf("%d ",p[i]);
return;
}
bool ok(int a,int b)
{
int aa[4],bb[4];
memset(aa,0,sizeof(aa));
memset(bb,0,sizeof(bb));
int i=0;
while(a!=0)
{
aa[i++]=a%10;
a/=10;
}
i=0;
while(b!=0) {bb[i++]=b%10;b/=10;}
int flag=0;
for(i=0;i<4;i++) if(aa[i]!=bb[i]) flag++;
if(flag!=1) return false;
return true;
}
void buildG()
{
int i,j,k;
memset(G,0,sizeof(G));
for(i=0;i<cnt;i++)
{
for(j=i+1;j<=cnt;j++)
{
if(ok(p[i],p[j])) G[i][j]=G[j][i]=1;
}
}
}
void bfs(int s)
{
int track[1300],dis[1300],visit[1300];
memset(visit,0,sizeof(visit));
memset(track,-1,sizeof(track));
int q[1300];
q[0]=s;
int head=0,tail=1,tmp=1;
int maxi=-1;
dis[s]=0;
visit[s]=1;
track[s]=s;
int step=0;
bool found=0;
int final;
while(head<tail && !found)
{
int x=q[head++];
for(int i=0;i<cnt;i++)
{
if(G[x][i]==1 && visit[i]==0)
{
visit[i]=1;
dis[i]=dis[x]+1;
track[i]=x;
if(dis[i]>maxi) maxi=dis[i];
if(p[i]==target) {final=x;found=1;break;}
q[tail++]=i;
}
}
}
if(!found) printf("Impossible\n");
else
{
printf("%d\n",maxi);
//while(track[final]!=final){printf("%d\n",p[final]); final=track[final];}
}
return;
}
int main()
{
//freopen("out.txt","w",stdout);
prim();
buildG();
int c,i;
scanf("%d",&c);
while(c--)
{
int s;
scanf("%d%d",&s,&target);
if(s==target) {printf("0\n");continue;}
for(i=0;i<cnt;i++) if(p[i]==s) break;
s=i;
bfs(s);
}
return 1;
}