题意：一个三维方块，给出高长宽，并且按照从最低面一层（或者从最顶面一层）到最高一层逐层给出这个方块的信息。S表示起点E表示终点，#表示这个格子不能走， .表示这个格子能走，走的方向有6个，前后左右上下。能是否能从起点走到终点，若能输出最少的步数
首先想到的DFS+剪枝，后来TLE了，才自己脑子又进水了，应该用BFS，因为剪枝的话效率不高，而且题目求最小步数，显然符合BFS的特点
从起点开始，将它能走的6个方向的格子且满足条件的格子入队，满足条件是指，这个格子还在方块内，而且能走，而且没有走过
一开始没有记录一个格子是否走过就TLE了，又脑子进水了显然是要记录的………………
如果队中某个格子就是终点的格子那么就跳出整个队列输出答案，如果到了最后队列为空了还没有找到终点，那么就是是失败的
队列中STL的queue来实现
#include <stdio.h> #include <string.h> #include <queue> using namespace std; #define N 35 bool g[N][N][N]; struct node { int z,x,y; int count,p; }; queue <struct node> q; int L,R,C; int sz,sx,sy,ez,ex,ey; int z[7]={0,0,0,0,0,1,-1} , x[7]={0,-1,1,0,0,0,0} , y[7]={0,0,0,-1,1,0,0}; void input() { int i,j,k; char s[N]; memset(g,0,sizeof(g)); sz=sx=sy=ez=ex=ey=0; for(i=1; i<=L ;i++) { for(j=1; j<=R; j++) { gets(s+1); for(k=1; k<=C; k++) if(s[k]=='S') { sz=i; sx=j; sy=k; } else if(s[k]=='E') { ez=i; ex=j; ey=k; } else if(s[k]=='#') g[i][j][k]=1; } gets(s+1); } return ; } void BFS() { struct node tmp,ttmp; int i,zz,xx,yy,pp,count,ok,ans; while(!q.empty()) q.pop(); g[sz][sx][sz]=1; tmp.z=sz; tmp.x=sx; tmp.y=sy; tmp.count=0; tmp.p=0; ok=0; q.push(tmp); while(!q.empty()) { tmp=q.front(); q.pop(); //printf("节点信息： z=%d x=%d y=%d 方向%d 步数%d\n",tmp.z,tmp.x,tmp.y,tmp.p,tmp.count); if(tmp.z==ez && tmp.x==ex && tmp.y==ey) { ok=1; ans=tmp.count; break;} for(i=1; i<=6; i++) { zz=tmp.z+z[i]; xx=tmp.x+x[i]; yy=tmp.y+y[i]; pp=i; count=tmp.count+1; if(!g[zz][xx][yy] && zz>=1 && zz<=L && xx>=1 && xx<=R && yy>=1 && yy<=C) { g[zz][xx][yy]=1; ttmp.z=zz; ttmp.x=xx; ttmp.y=yy; ttmp.p=pp; ttmp.count=count; q.push(ttmp); } } } if(!ok) printf("Trapped!\n"); else printf("Escaped in %d minute(s).\n",ans); return ; } int main() { while(scanf("%d%d%d",&L,&R,&C)!=EOF) { getchar(); if(!L && !R && !C) break; input(); BFS(); } return 0; }