Prime Path
题意：
给出两个四位素数 a , b。然后从a开始，每次可以改变四位中的一位数字，变成 c，c 可以接着变，直到变成b为止。要求 c 必须是素数。求变换次数的最小值。（a,b,c都是四位数字，输入时没有前导零）
分析：
- 每次改变可以获得一个四位数c，然后如果c是素数并且之前没有出现过，那么我们把它放入队列即可。
int f[10001];
int v[10001];
void init()//素数筛
{
memset(f,0,sizeof f);
for(int i=2;i<=10000;i++)
{
if(f[i]==0)
{
for(int j = i+i;j<=10000;j+=i)
{
f[j] = 1;
}
}
}
}
int a,b;
int bfs()
{
memset(v,0,sizeof v);
queue<int> q;
q.push(a);
v[a] = 1;
int tmp;
while(!q.empty())
{
tmp = q.front();q.pop();
if(tmp==b)return v[tmp];
int now;
int t = v[tmp]+1;
for(int i=0;i<=9;i++)//循环改变的数字 0 ~ 9
{
now = tmp - tmp%10+i;//改变个位
if(now>=1000&&f[now]==0&&v[now] == 0){v[now] = t;q.push(now);}
now = tmp/100*100+i*10+tmp%10;//改变十位
if(now>=1000&&f[now]==0&&v[now] == 0){v[now] = t;q.push(now);}
now = tmp/1000*1000+i*100+tmp%100;//改变百位
if(now>=1000&&f[now]==0&&v[now] == 0){v[now] = t;q.push(now);}
now = i*1000+tmp%1000;//改变千位
if(now>=1000&&f[now]==0&&v[now] == 0){v[now] = t;q.push(now);}
}
}
}
int main()
{
init();
int T;cin>>T;
while(T--)
{
cin>>a>>b;
int ans = bfs();
cout<<ans-1<<endl;
}
return 0;
}