1.题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=4255
2.参考代码:
#include <stdio.h> #include <cmath> #include <queue> #include <cstring> using namespace std; #define Max 40000 int prime[Max]; int map[200][200]; int sx,sy,ex,ey; int used[200][200]; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; struct node{ int x,y; int step; friend bool operator<(node n1,node n2){ return n1.step>n2.step; } }; void get_prime(){ int m=(int)sqrt(Max+0.5),c=0,i,j; memset(prime,0,sizeof(prime)); for(i=2;i<=m;i++) { if(!prime[i]) { for(j=i*i;j<=Max;j+=i) prime[j]=1; } } for(i=2;i<=Max;i++) prime[i]=!prime[i]; } void get_map(){ int n=120,i=0,j=0,t=n*n; memset(map,0,sizeof(map)); map[0][0]=t; while(t>1) { while(j+1<n && !map[i][j+1]) ///右 map[i][++j]=--t; while(i+1<n && !map[i+1][j]) ///下 map[++i][j]=--t; while(j-1>=0 && !map[i][j-1]) ///左 map[i][--j]=--t; while(i-1>=0 && !map[i-1][j]) ///上 map[--i][j]=--t; ///3和4的顺序 } } int bfs(){ priority_queue<node>q; memset(used,0,sizeof(used)); node cur,next; cur.x=sx; cur.y=sy; cur.step=0; int i; used[cur.x][cur.y]=1; q.push(cur); while(!q.empty()) { cur=q.top(); q.pop(); if(cur.x==ex && cur.y==ey) return cur.step; for(i=0;i<4;i++) { next.x=cur.x+dir[i][0]; next.y=cur.y+dir[i][1]; if(next.x>=0 && next.x<200 && next.y>=0 && next.y<200 && !used[next.x][next.y] && !prime[map[next.x][next.y]]) { next.step=cur.step+1; q.push(next); used[next.x][next.y]=1; } } } return -1; } int main() { int i,j,x,y,count=0,ans; get_prime(); get_map(); while(~scanf("%d %d",&x,&y)) { printf("Case %d: ",++count); for(i=0;i<200;i++) { for(j=0;j<200;j++) { if(map[i][j]==x) { sx=i; sy=j; } else if(map[i][j]==y) { ex=i; ey=j; } } } if(prime[map[sx][sy]] || prime[map[ex][ey]]) { printf("%d\n",ans); continue; } ans=bfs(); if(ans==-1) printf("impossible\n"); else printf("%d\n",ans); } return 0; }