2015
05-23

# A Famous Grid

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.)

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.

Each test case is described by a line of input containing two nonprime integer 1 <=x, y<=10,000.

Each test case is described by a line of input containing two nonprime integer 1 <=x, y<=10,000.

1 4
9 32
10 12

Case 1: 1
Case 2: 7
Case 3: impossible

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

#define Maxn 200

int graph[Maxn+5][Maxn+5];
int primeVis[Maxn*Maxn + 10];
int vis[Maxn*Maxn + 10];
int dis[Maxn*Maxn + 10];
int disx[4] = {0,1,0,-1};
int disy[4] = {-1,0,1,0};

struct Coord
{
//鏅�氭ā寮忎笅
int x,y;
}coord[Maxn*Maxn+10];

void init()
{
memset(primeVis,0,sizeof(primeVis));
}
void getPrimeVis()
{
//鍒繕浜�1涔熸槸鍚堟暟
primeVis[1] = 1;
for(int i=2;i<Maxn+5;i++)
{
if(!primeVis[i])
{
for(int j=i*i;j<=Maxn*Maxn;j+=i) primeVis[j] = 1;
}
}
}
//浠ユ櫘閫氭柟寮忓缓绔嬪浘锛岃�屼笉鏄绠楁満鏂瑰紡锛坹鍜寈鏄鍊掔殑锛�
void getMap()
{
int t = Maxn*Maxn;
int left = 1;
int right = Maxn;
int top = Maxn;
int bottom = 1;
while(t)
{
for(int i=left;i<=right;i++) {graph[i][top] = t--;coord[t+1].x = i;coord[t+1].y = top;}
top--;
for(int i=top;i>=bottom;i--) {graph[right][i] = t--;coord[t+1].x = right;coord[t+1].y = i;}
right--;
for(int i=right;i>=left;i--) {graph[i][bottom] = t--;coord[t+1].x = i;coord[t+1].y = bottom;}
bottom++;
for(int i=bottom;i<=top;i++) {graph[left][i] = t--;coord[t+1].x = left;coord[t+1].y = i;}
left++;
}

}

int bfs(int s,int t)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
queue<int> q;
q.push(s);
vis[s] = 1;
while(!q.empty())
{
int temp = q.front();
q.pop();
for(int i=0;i<4;i++)
{
int curx = coord[temp].x + disx[i];
int cury = coord[temp].y + disy[i];
if(curx>=1 && curx<=Maxn && cury>=1 && cury<=Maxn)
{
//鏈璁块棶杩囦笖鏄悎鏁�
int cur = graph[curx][cury];
if(vis[cur]==0 && primeVis[cur])
{
vis[cur] = 1;
dis[cur] = dis[temp] + 1;
if(cur == t) return dis[cur];
q.push(cur);
}
}
}
}
return -1;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n,m;
int a,b;
init();
getPrimeVis();
getMap();
int cas = 0;
while(scanf(" %d %d",&a,&b)!=EOF)
{
cas++;
printf("Case %d: ",cas);
int ans = bfs(a,b);
if(ans == -1) puts("impossible");
else printf("%d\n",ans);
}
return 0;
}

1. 你傻吗……男性是高高在上的一方，打毛男权旗… 在地球今天需要获得平等权利的就是女人啊，在地球今天女权和性别平权当然就是一回事了啊

2. 放下身心世界。即大布施。不复起贪嗔痴。即打持戒。不计是非人我。即大忍辱。不稍间断夹杂。即大精进。不复妄想驰逐。即大禅定。不为他歧所惑。即大智慧。