POJ2251 Dungeon Master

题目大意：给一个三维图，可以前后左右上下6种走法，走一步1分钟，求最少时间（其实就是最短路）
分析：DFS的话复杂度为O(6^n)会TLE）

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
char map[35][35][35];
int vis[35][35][35];
int X,Y,Z,sx,sy,sz,ex,ey,ez;
int dir[6][3] = {{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};
 int step[35][35][35];
struct node{
    int x,y,z;
};
int bfs(){
    node p,next;
    queue<node> Q;
    p.x = sx,p.y = sy,p.z = sz;

    step[sx][sy][sz]=0;
    vis[sx][sy][sz] = 1;
    Q.push(p);
    while(!Q.empty()){
        p = Q.front();
        Q.pop();
         if(map[p.x][p.y][p.z]=='E')
            return step[ex][ey][ez];//p.step;
        vis[p.x][p.y][p.z]=1;
        for(int i = 0; i<6; i++)
        {

            int dx = p.x+dir[i][0];
            int dy = p.y+dir[i][1];
            int dz = p.z+dir[i][2];
            //if(check(next.x,next.y,next.z))
            if(vis[dx][dy][dz]||map[dx][dy][dz]=='#'||dx<0||dx>=X||dy<0||dy>=Y||dz<0||dz>=Z)
                continue;
            vis[dx][dy][dz] = 1;
            next.x=dx,next.y=dy,next.z=dz;
            step[dx][dy][dz]=step[p.x][p.y][p.z]+1;//next.step = p.step+1;
            Q.push(next);
        }
    }
    return 0;
}
int main(){
    int i,j,r;
    while(scanf("%d%d%d",&X,&Y,&Z),X+Y+Z)
    {
        for(i = 0; i<X; i++)
        {
            for(j = 0; j<Y; j++)
            {
                scanf("%s",map[i][j]);
                for(r = 0; r<Z; r++)
                {
                    if(map[i][j][r] == 'S')
                    {
                        sx = i,sy = j,sz = r;
                    }
                    else if(map[i][j][r] == 'E')
                    {
                        ex = i,ey = j,ez = r;
                    }
                }
            }
        }
        memset(vis,0,sizeof(vis));
        int ans;
        ans = bfs();
        if(ans)
            printf("Escaped in %d minute(s).\n",ans);
        else
            printf("Trapped!\n");
    }

    return 0;
}