A Famous Grid
Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1562 Accepted Submission(s): 603
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.)
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.
Sample Input
1 4
9 32
10 12
Sample Output
Case 1: 1
Case 2: 7
Case 3: impossible
Source Fudan Local Programming Contest 2012
今天收获还算非常棒！下午独立a了两个稍微复杂点儿的搜索题。累的我肩旁脖子疼啊，晚上上完实验课操场跑了好几圈没啥用，腰酸背疼啊 ！
说说这个题，当时训练赛的时候很明确知道怎么做，但毕竟自己代码能力不强，写不出来干着急啊 ！从那天就很明确，做的题目太少，时间不能浪费在debug上。
这周就要省赛了~~心想上学期要开始acm 应该会比现在好的多，写完博客还得挂网课 ，马上网课就要结束了 ，一节还没上过。好了~，把代码放这了~~有问题大家交流~~
#include
#include
#include
using namespace std; const int M=110; // 设定一个全局常量非常方便 int cnt[M][M]; int primer[M*M]; int vis[M][M]; int s,e,t=0; int dir[][2]= {{0,1},{1,0},{-1,0},{0,-1}};//控制四个方向 struct node { int x,y,step; }; void prime() // 打印素数表 { memset(primer,0,sizeof(primer)); for(int i=2; i<=M; i++) { if(!primer[i]) for(int j=i*i; j<=M*M; j+=i) { primer[j]=1; } } primer[1]=1; } void inti() //初始化方格，把素数全都置为0，非素数按值存储 { memset(cnt,0,sizeof(cnt)); int tot=M*M; int x,y; x=0; y=0; cnt[0][0]=tot; while(tot>1) { while(y+1
=0&&!cnt[x][y-1]) { if(!primer[--tot]) { cnt[x][--y]=0; } else { y--; cnt[x][y]=tot; } } while(x-1>=0&&!cnt[x-1][y]) { if(!primer[--tot]) { cnt[--x][y]=0; } else { x--; cnt[x][y]=tot; } } } } void bfs(int x,int y) { queue
dict; node cur,next; cur.x=x; cur.y=y; cur.step=0; dict.push(cur); memset(vis,0,sizeof(vis)); // 初始化vis； vis[x][y]=1; //第一个点标记已经访问过。 int ok=1; while(!dict.empty()) { cur=dict.front(); dict.pop(); //调bug时发现拉下一次这个，结果导致无限循环 for(int i=0; i<4; i++) { int tx=cur.x+dir[i][0]; int ty=cur.y+dir[i][1]; if(tx>=0&&ty>=0&&tx