题意：更改四位数的门牌号(素数)，每次只能改一个数字，问最少多少次能改到目标数字。
思路：打表出四位的所有素数，然后建图，只有一个位数的数字不同的连边，跑最短路，，，
#include<iostream>
#include<stdio.h>
#include<queue>
#include<string.h>
const int N=10000;
const int inf=0x3fffffff;
using namespace std;
int link[N],prim[N],dis[N],vis[N];
struct edge
{
int st,ed,next;
}e[N*10];
int head[N],num;
void addedge(int x,int y)
{
e[num].st=x;e[num].ed=y;e[num].next=head[x];head[x]=num++;
e[num].st=y;e[num].ed=x;e[num].next=head[y];head[y]=num++;
}
bool judge(int x,int y)
{
int sum=0;
while(x)
{
if(x%10!=y%10)
sum++;
x/=10;y/=10;
}
if(sum==1)
return true;
return false;
}
int spfa(int s,int ed)
{
queue<int>Q;
int i,v,u;
for(i=1000;i<=9999;i++)
{
vis[i]=0;dis[i]=inf;
}
dis[s]=0;vis[s]=1;
Q.push(s);
while(!Q.empty())
{
u=Q.front();
Q.pop();
vis[u]=0;
if(u==ed)break;
for(i=head[u];i!=-1;i=e[i].next)
{
v=e[i].ed;
if(dis[v]>dis[u]+1)
{
dis[v]=dis[u]+1;
if(vis[v]==0)
{
Q.push(v);
vis[v]=1;
}
}
}
}
return dis[ed];
}
int main()
{
int i,j,k,t,a,b;
k=0;
for(i=2;i<N;i++)
{
if(link[i]==1)continue;
for(j=i+i;j<N;j+=i) link[j]=1;
if(i>999)
prim[k++]=i;
}
memset(head,-1,sizeof(head));
num=0;
for(i=0;i<k;i++)
{
for(j=i+1;j<k;j++)
if(judge(prim[i],prim[j]))
addedge(prim[i],prim[j]);
}
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&a,&b);
printf("%d\n",spfa(a,b));
}
return 0;
}