A Famous Grid
Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1496 Accepted Submission(s): 567
Problem Description
Mr. B 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.)
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. 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.
Input
Each test case is described by a line of input containing two nonprime integer 1 <=x, y<=10,000.
Output
For
each test case, display its case number followed by the length of the
shortest path or "impossible" (without quotes) in one line.
each test case, display its case number followed by the length of the
shortest path or "impossible" (without quotes) in one line.
Sample Input
1 4
9 32
10 12
Sample Output
Case 1: 1
Case 2: 7
Case 3: impossible
Source
/**
题意：给出两个数，问两点之间的最短距离
做法：蛇形矩阵 + bfs + 优先队列
**/
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <queue>
#define maxn 40000
using namespace std;
int mmap[][];
int a[][];
int vis[][];
int dx[] = {,,-,};
int dy[] = {,-,,};
int n,m;
bool num[maxn];
void is_prime()
{
int tot = ;
memset(num,false,sizeof(num));
num[] = true;
for(long long i=; i<maxn; i++)
{
if(!num[i])
{
for(long long j=i*i; j<=maxn; j+=i)
{
num[j] = true;
}
}
}
}
struct Node
{
int x;
int y;
int step;
Node() {}
Node(int _x,int _y,int _step)
{
x = ;
y = ;
step =;
}
} start,endd;
struct cmp
{
bool operator () (const Node &a,const Node &b)
{
return a.step>b.step;
}
};
int check(int x,int y)
{
if(x>= && x < && y >= && y < && num[a[x][y]] == true&& !vis[x][y]) return ;
return ;
}
priority_queue<Node,vector<Node>,cmp >que;
bool bfs()
{
memset(vis,,sizeof(vis));
Node tmp,now;
while(!que.empty()) que.pop();
que.push(start);
vis[start.x][start.y] = ;
start.step = ;
while(!que.empty())
{
now = que.top();
que.pop();
//cout<<now.x<<" "<<now.y<<" "<<now.step<<endl;
if(now.x == endd.x && now.y == endd.y)
{
endd.step = now.step;
return true;
}
for(int i=; i<; i++)
{
tmp.x = now.x + dx[i];
tmp.y = now.y + dy[i];
tmp.step = now.step + ;
if(check(tmp.x,tmp.y))
{
vis[tmp.x][tmp.y] = ;
que.push(tmp);
}
}
}
return false;
}
void init()
{
int x = ;
int y = ;
int nn = ;
int num=a[][]=;
while(num>)
{
while((y+)<nn&&!a[x][y+]) a[x][++y]= --num;
while((x+)<nn&&!a[x+][y]) a[++x][y]= --num;
while((y-)>=&&!a[x][y-]) a[x][--y]= --num;
while((x-)>=&&!a[x-][y]) a[--x][y]= --num; }
}
int main()
{
//freopen("in.txt","r",stdin);
init();
is_prime();
int Case = ;
while(~scanf("%d %d",&n,&m))
{
for(int i=; i<; i++)
{
for(int j=; j<; j++)
{
if(a[i][j] == n)
{
start.x = i;
start.y = j;
}
if(a[i][j] == m)
{
endd.x= i;
endd.y = j;
}
}
}
bool prime = false;
prime = bfs();
printf("Case %d: ",Case++);
if(prime) printf("%d\n",endd.step);
else printf("impossible\n");
}
return ;
}