题目链接：http://poj.org/problem?id=2251
知道你看不懂题（手动滑稽）：友情链接。
题意：找到从S到E的最少步数的路径，输出该步数，不过有意思的是这个类似迷宫问题不是二维的，是一个三维迷宫，其实三维迷宫和二维没多大差别，只是时间复杂度更多一点，搜索的方向更多一点，初次接触可能会被难住。
代码：
#include<stdio.h> #include<string.h> #include<iostream> #include<queue> using namespace std; struct node//定义三维坐标结构体 { int z; int x; int y; }; int dx[6]={0,-1,0,1,0,0},dy[6]={-1,0,1,0,0,0},dz[6]={0,0,0,0,-1,1};//六个方向的搜索 bool vis[31][31][31];//vis数组记录是否走过，剪枝去重。 char mp[31][31][31]; int d[31][31][31];//记录步数的三位数组。 int l,r,c,gx,gy,gz,sx,sy,sz;//g则是开始的坐标，S则是终止的坐标。 int bfs() { queue<node>q; q.push({gz,gx,gy}); vis[gz][gx][gy]=1; d[gz][gx][gy]=0; while(q.size()) { node p=q.front(); q.pop(); if(p.x==sx&&p.y==sy&&p.z==sz) break; for(int i=0;i<6;i++)//六个方向搜寻 { int nx=p.x+dx[i]; int ny=p.y+dy[i]; int nz=p.z+dz[i]; if(nx>=0&&nx<r&&nz>=0&&nz<l&&ny>=0&&ny<c&&!vis[nz][nx][ny]&&mp[nz][nx][ny]!='#') { q.push({nz,nx,ny});//如果满足就加入队列。 vis[nz][nx][ny]=1;//标记此坐标来过。 d[nz][nx][ny]=d[p.z][p.x][p.y]+1;//步数加一。 //printf("d:%d nx:%d ny:%d nz:%d\n",d[nz][nx][ny],nx,ny,nz);这个是我调试时用的 。 } } } return d[sz][sx][sy];//返回步数 。 } int main(void) { int sum; while(cin>>l>>r>>c) { memset(d,0,sizeof d);//初始化 memset(vis,0,sizeof vis);//初始化 if(l==0&&r==0&&c==0) break; for(int i=0;i<l;i++) { for(int j=0;j<r;j++) { for(int k=0;k<c;k++) { cin>>mp[i][j][k]; if(mp[i][j][k]=='S')//记录起点坐标。 { gz=i; gx=j; gy=k; mp[i][j][k]='.'; } if(mp[i][j][k]=='E')//记录终点坐标。 { sz=i; sx=j; sy=k; mp[i][j][k]='.'; } } } getchar(); } sum=bfs(); if(sum) printf("Escaped in %d minute(s).\n",sum); else printf("Trapped!\n"); } return 0; }
小结一下:这个题其实没有多难，就就是一个广搜，只不过这个三维地图可能有点唬人，不过还要掌握了广搜，这道题还是蛮简单的，不过我开始做的时候被卡了好久，最开始是觉得直接套模版可能会超时，后来发现其他的骚操作也想不到，然后就套模版，套模板的时候又被卡了几个小时，原因就在构建三维数组的时候Z轴搞错了，把数组的放置弄错了。