学步园

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=200;
int dis[maxn*maxn+10],m,n,map[maxn][maxn],loc[maxn*maxn+10],p[maxn*maxn+10];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void prime()
{
    for(int i=2;i*i<=maxn*maxn;i++)
    {
        if(!p[i])
        {
            for(int j=i*i;j<=maxn*maxn;j+=i) p[j]=1;
        }
    }
}
void build()
{
    int k,i,j,x,y;
    int tem=maxn*maxn;
    for(k=maxn,x=0,y=0;k>=2;k-=2,x++,y++)
    {
        for(i=x;i<k+x-1;i++)
        {
            map[y][i]=tem;
            loc[tem--]=i*maxn+y;
        }
        for(j=y;j<k+y-1;j++)
        {
            map[j][i]=tem;
            loc[tem--]=i*maxn+j;
        }
        for(;i>x;i--)
        {
            map[j][i]=tem;
            loc[tem--]=i*maxn+j;
        }
        for(;j>y;j--)
        {
            map[j][i]=tem;
            loc[tem--]=i*maxn+j;
        }
    }
}
int bfs()
{
    queue<int> q;
    int s=loc[m],t=loc[n];
    dis[s]=0;
    q.push(s);
    int i;
    while(!q.empty())
    {
        if(q.front()==t) return dis[t];
        int x=q.front()/maxn,y=q.front()%maxn;
        int l=q.front();
        q.pop();
        int tx,ty,tl;
        for(i=0;i<4;i++)
        {
            tx=x+dir[i][0];
            ty=y+dir[i][1];
            tl=(tx*maxn+ty)%(maxn*maxn);
            if(tx<maxn&&tx>=0&&ty<maxn&&ty>=0&&p[map[ty][tx]]&&dis[tl]==-1)//血的代价，以后一定要注意判断语句的先后顺序
            {
                dis[tl]=dis[l]+1;
                q.push(tl);
            }
        }

    }
    return -1;
}
int main()
{
    memset(p,0,sizeof(p));
    p[1]=1;
    prime();
    build();
    int tot=1;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(dis,-1,sizeof(dis));
        int rel=bfs();
        if(rel==-1) printf("Case %d: impossible\n",tot++);
        else printf("Case %d: %d\n",tot++,rel);
    }
    return 0;
}