题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4255
题意描述:在一个蛇形矩阵中,素数的格子不能走,问从一个合数到另一个合数最少需要几步,没有解时输出impossible。
题目分析:1、因为素数的地方不能走,所以需要打印素数表;
         2、蛇形矩阵需要打印,这里我做了一个处理,定义了一个结构体G,把每个数所在的位置保存了下来,然后就没有去打印蛇形矩阵,而把0-1关系矩阵给出,其实打印蛇形矩阵也可以;
         3、这里最好用广搜来做,深搜会超时,(我一直都怕深搜超时);
         4、数据给的两个数在10000范围内,但是如果只打印100*100的蛇形矩阵,保管会死翘翘,因为人家没有告诉你蛇形矩阵的范围,你必须打印到足够大才可以,我打印到了200*200,网上有人说打印到400*400的。

代码如下:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>

using namespace std;

#define MAX 40000
#define MAZ 200

int prime[MAX];

     //标记素数,素数为0,合数为1
bool vis[MAZ+5][MAZ+5];      //标记蛇形矩阵关系,1表示是素数,0表示合数
bool v[MAZ+5][MAZ+5];       //标记找最小路时是否走过
struct G{
   int x,y;
}grap[MAX+1];    //记录蛇形矩阵中数的位置

int dir[4][2]={ {-1,0},{1,0},{0,-1},{0,1} };     //允许走的四个方向
int xx,yy;

//打印素数表
void InitPrime(){
   int i,j;
   memset( prime, 0, sizeof(prime) );
   prime[0] = prime[1] = 1;
   for( i=2; i<MAX+1; i++ ){
       if( !prime[i] ){
           for( j=i+i; j<MAX+1; j+=i )
               prime[j] = 1;
       }
   }
}

//创建蛇形矩阵关系图vis,并在结构体grap中存储其出现的位置
void InitMap(){
   int l = 1, r = MAZ;
   int u = 1, d = MAZ;
   int sum = MAX;
   int i;
   memset( vis, 0, sizeof(vis) );
   while( sum>0 ){
       for( i=l; i<=r; i++ ){
           grap[sum].x = u;
           grap[sum].y = i;
           if( !prime[sum] )
               vis[u][i] = 1;
           else
               vis[u][i] = 0;
           sum –;
       }
       u ++;
       for( i=u; i<=d; i++ ){
           grap[sum].x = i;
           grap[sum].y = r;
           if( !prime[sum] )
               vis[i][r] = 1;
           else
               vis[i][r] = 0;
           sum –;
       }
       r –;
       for( i=r; i>=l; i– ){
           grap[sum].x = d;
           grap[sum].y = i;
           if( !prime[sum] )
               vis[d][i] = 1;
           else
               vis[d][i] = 0;
           sum –;
       }
       d –;
       for( i=d; i>=u; i– ){
           grap[sum].x = i;
           grap[sum].y = l;
           if( !prime[sum] )
               vis[i][l] = 1;
           else
               vis[i][l] = 0;
           sum –;
       }
       l ++;
   }
}

//广搜最小步数,网上很多人是把走到某一点时的横纵坐标、步数放到一个结构体里,定义一个结构体队列,写起来貌似简单了很多
int BFS( int su, int sv, int eu, int ev ){
   int xu,yv,i;
   int cnt = 0;
   queue<int>Q;
   memset( v, 0, sizeof(v) );
   Q.push( su );   Q.push( sv );   Q.push( cnt );
   v[su][sv] = 1;
   while( !Q.empty() ){
       xu = Q.front();   Q.pop();
       yv = Q.front();   Q.pop();
       cnt = Q.front();  Q.pop();
       if( xu ==eu && yv == ev ){
           return cnt;
       }
       for( i=0; i<4; i++ ){
           int xxu = xu + dir[i][0];
           int yyv = yv + dir[i][1];
           if( (xxu>0 && xxu<=MAZ) && (yyv>0 && yyv<=MAZ) && !v[xxu][yyv] && !vis[xxu][yyv] ){     //边界判断一定要加上
               Q.push( xxu );
               Q.push( yyv );
               Q.push( cnt+1 );
               v[xxu][yyv] = 1;
           }
       }
   }
   return 0;
}

int main(){
   int ncase=1;
   int step;
   InitPrime();
   InitMap();
   while( scanf( “%d%d”,&xx,&yy ) == 2 ){
       printf( “Case %d: “, ncase++ );
       step = BFS( grap[xx].x, grap[xx].y, grap[yy].x, grap[yy].y );
       if( step == 0 )
           printf( “impossible\n” );
       else
           printf( “%d\n”, step );
   }
   return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation