??? BFS得到的一定是最短路徑。開始我還在糾結怎么才是最短的呢。其實BFS的題目有個共性（這不廢話，哪一類題沒有共性啊。呵呵）。以后做這種題自己慢慢總結吧。
?
?? 這題的思路就是寫枚舉出4位數的所有prime number，用個數組p[]標記。再用個數組visit[]標記某個數是否被訪問過，避免重復訪問.然后就是對這四位數的每一位進行BFS啦！
poj1741？?
#include <iostream>
#include <cstdio>
#include <queue>
#include <fstream>
#include <memory.h>
using namespace std;
int p[10000],visit[10000];
int n,a,b;
int Index[4];
struct node
{
int num,step;
}ans[10000];
bool prime(int n)
{
for(int i=2; i*i<=n ; i++)
{
if(n%i==0)
return false;
}
return true;
}
int bfs()
{
int j=0,i;
queue<node> q;
ans[j].num=a;
ans[j].step=0;
visit[a]=1;
q.push(ans[j]);
while(!q.empty())
{
node next;
next=q.front();
q.pop();
if(next.num==b)
{
return next.step;
}
Index[0]=next.num/1000; Index[1]=(next.num%1000)/100;
Index[2]=(next.num%100)/10; Index[3]=next.num%10;
for(i=0 ; i<10 ;i++)
{
if(i==Index[3])
continue;
int l=next.num+i-Index[3];
if(!visit[l] && p[l])
{
ans[++j].num=l;
ans[j].step=next.step+1;
visit[l]=1;
q.push(ans[j]);
}
}
for(i=0 ; i<10 ;i++)
{
if(i==Index[2])
continue;
int l=next.num+(i-Index[2])*10;
if(!visit[l] && p[l])
{
ans[++j].num=l;
ans[j].step=next.step+1;
visit[l]=1;
q.push(ans[j]);
}
}
for(i=0 ; i<10 ;i++)
{
if(i==Index[1])
continue;
int l=next.num+(i-Index[1])*100;
if(!visit[l] && p[l])
{
ans[++j].num=l;
ans[j].step=next.step+1;
visit[l]=1;
q.push(ans[j]);
}
}
for( i=0 ; i<10 ;i++)
{
if(i==Index[0])
continue;
int l=next.num+(i-Index[0])*1000;
if(!visit[l] && p[l])
{
ans[++j].num=l;
ans[j].step=next.step+1;
visit[l]=1;
q.push(ans[j]);
}
}
}
}
int main()
{
freopen("acm.txt","r",stdin);
memset(p,0,sizeof(p));
scanf("%d",&n);
for(int i=1000; i<10000; i++)
{
if(prime(i))
p[i]=1; //is prime number
}
while(n--)
{
memset(visit,0,sizeof(visit));
scanf("%d%d",&a,&b);
printf("%d\n",bfs());
}
return 0;
}
?
