先生成蛇型矩阵，然后再筛选出素数进行标记，最后bfs。这里要注意题目要求的1-10000的之间的数路径，但是并不代表我们只要打印到这个范围的素数，因为很可能边沿的点需要走到外面的图形来完成对短路，外围的也不要打印太多，毕竟素数的个数越到外面是越稀疏的，所以打印到40000足矣。开始生成素数时1—10000结果wa了！！
代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
using namespace std;
int x2,y2;
int g[202][202],dx[4]={1,-1,0,0},dy[4]={0,0,-1,1};
int vis[202][202];
struct zhang
{
int x,y,bu;
};
void noprime(int x,int y)
{
int f=0 ;
if(g[x][y]==1)
g[x][y]=1 ;
else
{
for(int i=2;i<=sqrt(g[x][y]);i++)
if(g[x][y]%i==0)
{
f=1;
break;
}
if(f==0)
g[x][y]=0 ;
}
}
int bfs(int x,int y)
{
queue<zhang>q;
zhang current,next;
memset(vis,0,sizeof(vis));
current.x=x;
current.y=y;
current.bu=0;
q.push(current);
while(!q.empty())
{
current=q.front();
q.pop();
for(int i=0;i<4;i++)
{
next.x=current.x+dx[i];
next.y=current.y+dy[i];
if(next.x>=0&&next.x<200&&next.y>=0&&next.y<200&&!vis[next.x][next.y]&&g[next.x][next.y])
{
next.bu=current.bu+1;
vis[next.x][next.y]=1;
if(next.x==x2&&next.y==y2)
return next.bu;
q.push(next);
}
}
}
return -1 ;
}
int main()
{
int a1=-1,a2=200,a3=200,a4=-1;
int x=40000,i,j;
for(i=0;i<100;i++)
{
a1++;
for(j=a1;j<200-a1-1;j++)
g[a1][j]=x-- ;
a2--;
for(j=a1;j<200-a1-1;j++)
g[j][a2]=x-- ;
a3--;
for(j=200-a1-1;j>a1;j--)
g[a3][j]=x-- ;
a4++;
for(j=200-a1-1;j>a1;j--)
g[j][a4]=x-- ;
}
for(i=0;i<200;i++)
for(j=0;j<200;j++)
noprime(i,j) ;//标记素数！！
int n,m,x1,y1,t=0;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<200;i++)
for(j=0;j<200;j++)
if(g[i][j]==n)
{
x1=i;
y1=j;
}
else if(g[i][j]==m)
{
x2=i;
y2=j;
}
printf("Case %d: ",++t) ;
if(n==m)
{
printf("0\n");
continue;
}
int min=bfs(x1,y1) ;
if(min==-1)
printf("impossible\n");
else printf("%d\n",min);
}
return 0 ;
}