题目描述
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.
输出
For each test case, display its case number followed by the length of the shortest path or “impossible” (without quotes) in one line.
样例输入 Copy
1 4
9 32
10 12
样例输出 Copy
Case 1: 1
Case 2: 7
Case 3: impossible
题意：
给一个螺旋矩阵，每次都只能走非素数的格子，求两个数之间的最短距离。
思路：
首先是考虑如何将这个螺旋矩阵存到数组里，因为在以后需要根据某数的值查找这个数的横纵坐标，在这里用的是map和pair的结合来判断。
int num=106*106,n=106,m=106,j,i; for(i=0;i<m/2;i++) { for(j=i;j<n-i;j++) a[i][j]=num,mp[num]={i,j},num--; for(j=i+1;j<m-i;j++) a[j][n-i-1]=num,mp[num]={j,n-i-1},num--; for(j=n-i-2;j>i;j--) a[m-i-1][j]=num,mp[num]={m-i-1,j},num--; for(j=m-i-1;j>i;j--) a[j][i]=num,mp[num]={j,i},num--; }
对于查找两个数之间的距离可以直接用BFS。
本题的坑点就是在存储矩阵的时候如果只打印100 * 100可能就会误判，题目已经说明了是无限大的网格，给出的只是一部分，所以就会存在有一种情况，当打印100*100的矩阵的时候无法到达，当在外圈多打印几圈时，就可以出去再回来，这样是可以到达的。
代码：
#pragma GCC optimize(3) #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll #define x first #define y second inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int inf=0x3f3f3f3f,mod=1e9+7; const ll INF = 0x3f3f3f3f3f3f3f3f; const int maxn=1100,maxm=1e5+7; const double PI = atan(1.0)*4; int a[maxn][maxn]; map<int,PII>mp; int res[maxn][maxn]; struct node{ int x,y,dis; }; queue<node>q; bool vis[maxm];//标记非素数 int primer[maxm/10];//存素数 int cnt=0;//记录素数个数 int sx,sy,ex,ey; int aa[maxn][maxn]; void find_primer(){ vis[1]=1; for(int i=2;i<=maxm;i++){ if(!vis[i])primer[cnt++]=i;//0是素数 for(int j=0;j<cnt&&primer[j]*i<=maxm;j++){ vis[i*primer[j]]=1; if(i%primer[j]==0) break; } } } void init(){ int num=106*106,n=106,m=106,j,i; for(i=0;i<m/2;i++) { for(j=i;j<n-i;j++) a[i][j]=num,mp[num]={i,j},num--; for(j=i+1;j<m-i;j++) a[j][n-i-1]=num,mp[num]={j,n-i-1},num--; for(j=n-i-2;j>i;j--) a[m-i-1][j]=num,mp[num]={m-i-1,j},num--; for(j=m-i-1;j>i;j--) a[j][i]=num,mp[num]={j,i},num--; } /* for(i=0;i<m;i++) { for(j=0;j<n;j++) printf("%4d",a[i][j]); cout<<endl; }*/ } int nx[4]={0,0,1,-1}; int ny[4]={1,-1,0,0}; void bfs(int x,int y){ while(!q.empty()){ node t=q.front();q.pop(); int qx=t.x,qy=t.y; ///cout<<qx<<" "<<qy<<endl; if(qx==ex&&qy==ey){ return ; } for(int i=0;i<4;i++){ int xx=qx+nx[i],yy=qy+ny[i]; int tt=a[xx][yy]; if(!aa[xx][yy]&&vis[tt]&&xx>=0&&xx<106&&yy>=0&&yy<106){ res[xx][yy]=res[qx][qy]+1; q.push({xx,yy,res[xx][yy]}); aa[xx][yy]=1; } } } } int main(){ find_primer(); init();///构造矩阵 /// cout<<mp[56].first<<" "<<mp[56].second<<endl; int st,ed; int Case=1; while(~scanf("%d%d",&st,&ed)){ if(vis[st]==0||vis[ed]==0) { printf("Case %d: ",Case++); puts("impossible"); continue; } if(st==ed){ printf("Case %d: ",Case++); puts("0"); continue; } sx=mp[st].first,sy=mp[st].second; ex=mp[ed].first,ey=mp[ed].second; /// cout<<st<<" "<<sx<<" "<<sy<<endl; /// cout<<ed<<" "<<ex<<" "<<ey<<endl; printf("Case %d: ",Case++); memset(res,0,sizeof res); memset(aa,0,sizeof aa); while(!q.empty()) q.pop(); q.push({sx,sy,0}); aa[sx][sy]=1; bfs(sx,sy); if(res[ex][ey]==0) puts("impossible"); else out(res[ex][ey]),puts(""); } return 0; }
