POJ - 2251 Dungeon Master（三维BFS）

POJ - 2251 Dungeon Master（三维BFS）http://poj.org/problem?id=2251

题意： 给定一个三维空间，一个起点和终点，还有若干障碍物，人物从起点开始，只能往上下左右前后六个方向移动，问能否达到终点，若能，输出最短步数

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;const int N = 110;char g[N][N][N];
int l,r,c,dist[N][N][N];struct Node
{
    int x,y,z;
}st,ed;const int dx[]={
    -1,1,0,0,0,0};
const int dy[]={
    0,0,-1,1,0,0};
const int dz[]={
    0,0,0,0,-1,1};void bfs()
{
    memset(dist,-1,sizeof dist);queue<Node> Q;Q.push(st);dist[st.x][st.y][st.z]=0;while(Q.size()){
    Node t=Q.front();Q.pop();for(int i=0;i<6;i++){
    int x=t.x+dx[i],y=t.y+dy[i],z=t.z+dz[i];if(x<0||x>=l||y<0||y>=r||z<0||z>=c) continue;if(dist[x][y][z]!=-1) continue;if(g[x][y][z]=='#') continue;dist[x][y][z]=dist[t.x][t.y][t.z]+1;Q.push((Node){
    x,y,z});}}
}int main()
{
    while(cin>>l>>r>>c,l+r+c){
    memset(g,0,sizeof g);for(int i=0;i<l;i++)for(int j=0;j<r;j++)for(int k=0;k<c;k++){
    cin>>g[i][j][k];if(g[i][j][k]=='S') st=(Node){
    i,j,k};if(g[i][j][k]=='E') ed=(Node){
    i,j,k};}bfs();if(dist[ed.x][ed.y][ed.z]==-1) cout<<"Trapped!"<<endl;else cout<<"Escaped in "<<dist[ed.x][ed.y][ed.z]<<" minute(s)."<<endl;}return 0;
}