http://www.bnuoj.com/bnuoj/problem_show.php?pid=25662
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue> #define N 150
using namespace std; struct Nod
{
int x,y,step;
}node[]; int map[N][N];
int mark[N][N];
int prim[]; int cx[]={,,-,};
int cy[]={,,,-}; int cnt=; void getMap(int x,int y,int re)
{
while()
{
int dx,dy;
dx = x + cx[(re+)%];
dy = y + cy[(re+)%];
if(!(dx>=&&dx<N&&dy>=&&dy<N))
{
break;
}
if(map[dx][dy]==)
{
map[dx][dy]= ++cnt;
node[cnt].x = dx;
node[cnt].y = dy;
// getMap(dx,dy,(re+1)%4);
x = dx;
y = dy;
re = (re+)%;
}
else
{
dx = x + cx[re%];
dy = y + cy[re%];
if(!(dx>=&&dx<N&&dy>=&&dy<N))
{
break ;
}
map[dx][dy]= ++cnt;
node[cnt].x = dx;
node[cnt].y = dy;
// getMap(dx,dy,re);
x = dx;
y = dy;
}
}
} int bfs(int x,int y)
{
memset(mark,,sizeof(mark));
queue<Nod> Q;
Nod temp;
temp.x = node[x].x;
temp.y = node[x].y;
temp.step = ;
Q.push(temp);
mark[temp.x][temp.y] = ;
while(!Q.empty())
{
Nod td = Q.front();
Q.pop();
if(td.x==node[y].x&&td.y==node[y].y)
{
return td.step;
}
int i;
for(i=;i<;i++)
{
temp.x = td.x + cx[i];
temp.y = td.y + cy[i];
temp.step = td.step + ;
if(map[temp.x][temp.y]>=&&map[temp.x][temp.y]<=&&prim[map[temp.x][temp.y]]&&!mark[temp.x][temp.y])
{
mark[temp.x][temp.y]=;
Q.push(temp);
}
}
}
return -;
} int main()
{
cnt=;
int cas=;
map[][]=;
getMap(,,);
node[].x = ;
node[].y = ;
// cout<<cnt<<endl;
int i,j;
prim[]=;
for(i=;i<;i++)
{
for(j=;j*j<=i;j++)
{
if(i%j==)
{
prim[i]=;
break;
}
}
}
// for(i=1;i<=100;i++)
// if(!prim[i])cout<<i<<" "; int x,y;
while(~scanf("%d%d",&x,&y))
{
printf("Case %d: ",cas++);
int ans = bfs(x,y);
if(ans==-)
{
puts("impossible");
}
else
{
printf("%d\n",ans);
}
} return ;
}