HDU 4255 A Famous Grid

题目链接~~>

                 先生成蛇型矩阵，然后再筛选出素数进行标记，最后bfs。这里要注意题目要求的1-10000的之间的数路径，但是并不代表我们只要打印到这个范围的素数，因为很可能边沿的点需要走到外面的图形来完成对短路，外围的也不要打印太多，毕竟素数的个数越到外面是越稀疏的，所以打印到40000足矣。开始生成素数时1—10000结果wa了！！     

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      int x2,y2;
     
    
   

    

     

    
    

     

      int g[202][202],dx[4]={1,-1,0,0},dy[4]={0,0,-1,1};
     
    
   

    

     

    
    

     

      int vis[202][202];
     
    
   

    

     

    
    

     

      struct zhang
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,y,bu;
     
    
   

    

     

    
    

     

      };
     
    
   

    

     

    
    

     

      void noprime(int x,int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int f=0 ;
     
    
   

    

     

    
    

     
 if(g[x][y]==1)
     
    
   

    

     

    
    

     

       g[x][y]=1 ;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(int i=2;i<=sqrt(g[x][y]);i++)
     
    
   

    

     

    
    

     
 if(g[x][y]%i==0)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       f=1;
     
    
   

    

     

    
    

     
 break;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(f==0)
     
    
   

    

     

    
    

     

       g[x][y]=0 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int bfs(int x,int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 queue<zhang>q;
     
    
   

    

     

    
    

     

       zhang current,next;
     
    
   

    

     

    
    

     
 memset(vis,0,sizeof(vis));
     
    
   

    

     

    
    

     

       current.x=x;
     
    
   

    

     

    
    

     

       current.y=y;
     
    
   

    

     

    
    

     

       current.bu=0;
     
    
   

    

     

    
    

     

       q.push(current);
     
    
   

    

     

    
    

     
 while(!q.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       current=q.front();
     
    
   

    

     

    
    

     

       q.pop();
     
    
   

    

     

    
    

     
 for(int i=0;i<4;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       next.x=current.x+dx[i];
     
    
   

    

     

    
    

     

       next.y=current.y+dy[i];
     
    
   

    

     

    
    

     
 if(next.x>=0&&next.x<200&&next.y>=0&&next.y<200&&!vis[next.x][next.y]&&g[next.x][next.y])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       next.bu=current.bu+1;
     
    
   

    

     

    
    

     

       vis[next.x][next.y]=1;
     
    
   

    

     

    
    

     
 if(next.x==x2&&next.y==y2)
     
    
   

    

     

    
    

     
 return next.bu;
     
    
   

    

     

    
    

     

       q.push(next);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return -1 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int a1=-1,a2=200,a3=200,a4=-1;
     
    
   

    

     

    
    

     
 int x=40000,i,j;
     
    
   

    

     

    
    

     
 for(i=0;i<100;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       a1++;
     
    
   

    

     

    
    

     
 for(j=a1;j<200-a1-1;j++)
     
    
   

    

     

    
    

     

       g[a1][j]=x-- ;
     
    
   

    

     

    
    

     

       a2--;
     
    
   

    

     

    
    

     
 for(j=a1;j<200-a1-1;j++)
     
    
   

    

     

    
    

     

       g[j][a2]=x-- ;
     
    
   

    

     

    
    

     

       a3--;
     
    
   

    

     

    
    

     
 for(j=200-a1-1;j>a1;j--)
     
    
   

    

     

    
    

     

       g[a3][j]=x-- ;
     
    
   

    

     

    
    

     

       a4++;
     
    
   

    

     

    
    

     
 for(j=200-a1-1;j>a1;j--)
     
    
   

    

     

    
    

     

       g[j][a4]=x-- ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(i=0;i<200;i++)
     
    
   

    

     

    
    

     
 for(j=0;j<200;j++)
     
    
   

    

     

    
    

     

       noprime(i,j) ;//标记素数！！
     
    
   

    

     

    
    

     
 int n,m,x1,y1,t=0;
     
    
   

    

     

    
    

     
 while(scanf("%d%d",&n,&m)!=EOF)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(i=0;i<200;i++)
     
    
   

    

     

    
    

     
 for(j=0;j<200;j++)
     
    
   

    

     

    
    

     
 if(g[i][j]==n)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       x1=i;
     
    
   

    

     

    
    

     

       y1=j;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(g[i][j]==m)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       x2=i;
     
    
   

    

     

    
    

     

       y2=j;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("Case %d: ",++t) ;
     
    
   

    

     

    
    

     
 if(n==m)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("0\n");
     
    
   

    

     

    
    

     
 continue;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int min=bfs(x1,y1) ;
     
    
   

    

     

    
    

     
 if(min==-1)
     
    
   

    

     

    
    

     
 printf("impossible\n");
     
    
   

    

     

    
    

     
 else printf("%d\n",min);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/12019325