hdu 1240 Asteroids! 三维迷宫 bfs

题目意思：三维的迷宫，寻找最短路径从给定的起点到终点

解题思路：bfs  只是这里是三维 搜索方向由原来的4个变成6个

code：

//改成广度优先搜索
 
#include
#include
const int max=1000005;
const int size=10;
char D[size][size][size];
bool f[size][size][size];
int p[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int n,flag,an,x1,y1,z1,x2,y2,z2;
typedef struct da
{
  int x,y,z;
  int step;       
}da;

da que[max];

int main()
{
    char ch[15];
    int i,j,k,x,y,z,st,en,p1,p2,step;
   while(scanf("%s%d",ch,&n)!=EOF)
   {
   for(i=0;i     {
       for(j=0;j       scanf("%s",D[i][j]);         
     } 

   //注意这里的顺序 三维注意下
   scanf("%d%d%d",&y1,&z1,&x1);                           
   scanf("%d%d%d",&y2,&z2,&x2);  
   scanf("%s",ch);
   //printf("x2=%d y2=%d z2=%d\n",x2,y2,z2);
   memset(f,0,sizeof(f));
   flag=0;an=1005;
   st=0;en=1;
   que[en].x=x1;que[en].y=y1;que[en].z=z1;
   que[en].step=0;
   f[x1][y1][z1]=true;
   flag=0;
   while(st   {
     p1=p2=en;
     for(i=st+1;i<=en;i++) //可以改进成循环队列
     {
     //对每个出战
     x=que[i].x;y=que[i].y;z=que[i].z;
     step=que[i].step;
     if(x==x2&&y==y2&&z==z2)
     {an=step;flag=1;goto loop;}
       for(j=0;j<6;j++)
       {
       if(x+p[j][0]<0||x+p[j][0]>=n||y+p[j][1]<0||y+p[j][1]>n||z+p[j][2]<0||z+p[j][2]>=n)
       continue;
       if(f[x+p[j][0]][y+p[j][1]][z+p[j][2]]==true) continue;
       if(D[x+p[j][0]][y+p[j][1]][z+p[j][2]]=='O')
       {
       que[++p2].x=x+p[j][0];que[p2].y=y+p[j][1];que[p2].z=z+p[j][2];
       que[p2].step=step+1;  
       f[que[p2].x][que[p2].y][que[p2].z]=true;                                       
       }               
       }                  
     }
     st=p1;en=p2;
   }
loop:
   if(flag) printf("%d %d\n",n,an);
   else printf("NO ROUTE\n");
   }   
}