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
-
<span style="color:#cc9933;"> <span style="font-family: 'Times New Roman';">traveling from a prime number is disallowed 题目这句话比较坑 起点可以是素数</span></span> -
<span style="color:#464646;"> #include<cstdio> #include<cstdlib> #include<cstring> #include<queue> using namespace std; const int maxn=11000; int isprime[maxn],starx,stary,endx,endy,vis[100][100],ans; int a[100][100],mov[][2]={1,0,-1,0,0,1,0,-1},dist[100][100]; void count(){int j,i;isprime[1]=1;for(i=2;i*i<maxn;++i){if(isprime[i])continue;for(j=i*i;j<maxn;j+=i)isprime[j]=1;} } void map(){int i=0,j=0;a[0][0]=10000;while(1){while(1){a[i][++j]=a[i][j-1]-1;if(j>=99||a[i][j+1]!=0||a[i][j]==1)break;}if(a[i][j]==1)break;while(1){a[++i][j]=a[i-1][j]-1;if(i>=99||a[i+1][j]!=0||a[i][j]==1)break;}if(a[i][j]==1)break;while(1){a[i][--j]=a[i][j+1]-1;if(j<=0||a[i][j-1]!=0||a[i][j]==1)break;}if(a[i][j]==1)break;while(1){a[--i][j]=a[i+1][j]-1;if(i<=0||a[i-1][j]!=0||a[i][j]==1)break;}if(a[i][j]==1)break;} } void find(int m,int n ){int i,j;for(i=0;i<100;++i){for(j=0;j<100;++j){if(a[i][j]==m){starx=i;stary=j;}if(a[i][j]==n){endx=i;endy=j;}}} } int BFS(int x,int y){vis[x][y]=1;queue<int>Q;int xx,yy,q;q=x*100+y;Q.push(q);while(!Q.empty()){q=Q.front();Q.pop();x=q/100;y=q%100;for(int i=0;i<4;++i){xx=x+mov[i][0];yy=y+mov[i][1];if(xx>=0&&xx<100&&yy>=0&&yy<100&&isprime[a[xx][yy]]==1&&vis[xx][yy]==0){vis[xx][yy]=1;if(xx==endx&&yy==endy)return dist[x][y]+1;dist[xx][yy]=dist[x][y]+1;Q.push(xx*100+yy);}}}return -1; } int main() {map();count();int m,n,t=1,p;while(scanf("%d%d",&m,&n)!=EOF){find(m,n);ans=0;memset(vis,0,sizeof(vis));memset(dist,0,sizeof(dist));p=BFS(starx,stary);if(p==-1)printf("Case %d: impossible\n",t++);elseprintf("Case %d: %d\n",t++,p);}return 0; } </span>