spiral grid
时间限制：2000 ms | 内存限制：65535 KB
难度：4
描述
Xiaod has recently discovered the grid named "spiral grid".
Construct the grid like the following figure. (The grid is actually infinite. The figure is only a small part of it.)
Considering traveling in it, you are free to any cell containing a composite number or 1, but traveling to any cell containing a prime number is disallowed. In addition, traveling from a prime number is disallowed, either. You can travel up, down, left or right, but not diagonally. Write a program to find the length of the shortest path between pairs of nonprime numbers, or report it's impossible.
输入
Each test case is described by a line of input containing two nonprime integer 1 <=x, y<=10,000.
输出
For each test case, display its case number followed by the length of the shortest path or "impossible" (without quotes) in one line.
样例输入
1 4
9 32
10 12
样例输出
Case 1: 1
Case 2: 7
Case 3: impossible
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
int map[105][105]={0};
int mm=10000,n=100;
int fir,end,loop[105][105];
int prime[11000]={1,1,0};
int sx[]={0,0,1,-1},zy[]={1,-1,0,0};
void Build_map() //建立地图
{
int i,j,k;
for(i=1;i<=(n+1)/2;i++)
{
for(j=1;j<=n-2*i+2;j++)
map[i][j+i-1]=mm--;
for(j=1;j<=n-2*i;j++)
map[j+i][n-i+1]=mm--;
for(j=n-i+1;j>=i;j--)
map[n-i+1][j]=mm--;
for(j=n-i;j>=i+1;j--)
map[j][i]=mm--;
}
}
void printf_map()//打印地图
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d ",map[i][j]);
printf("
");
}
}
void judge_prime() //筛选法打个素数表
{
int i,j;
for(i=2;i<=10000;i++)
{
if(prime[i]==0)
{
for(j=i+i;j<=10000;j+=i)
prime[j]=1;
}
}
}
struct coordinate
{
int x;
int y;
int step;
}t1;
void find() //找到 fir 的坐标，存在 t1 中
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(map[i][j]==fir)
{
t1.x=i;
t1.y=j;
loop[i][j]=1;
t1.step=0;
return;
}
}
}
int bfs()
{
int i,j,step,x,y;
queue<coordinate> Q;
Q.push(t1);
while(!Q.empty())
{
i=Q.front().x;
j=Q.front().y;
step=Q.front().step;
Q.pop();
if(map[i][j]==end)
return step;
for(int a=0;a<4;a++)
{
x=i+sx[a];
y=j+zy[a];
if(map[x][y]!=0&&prime[map[x][y]]==1&&loop[x][y]==0)
{
coordinate t2={x,y,step+1};
Q.push(t2);
loop[x][y]=1;
}
}
}
return 0;
}
int main()
{
int i,j,nn=0;
Build_map();
judge_prime();
//printf_map();
while(~scanf("%d%d",&fir,&end))
{
nn++;
memset(loop,0,sizeof(loop));
find();
int ans=bfs();
if(ans)
printf("Case %d: %d
",nn,ans);
else
printf("Case %d: impossible
",nn);
}
}