POJ 2251 Dungeon Master(BFS)

题意：有一个三维的迷宫，可以上下左右前后六种方式行走，每移动一格需要耗费一分钟，# 代表墙（无法到达的地方），S代表起点，E代表终点，问你能否从起点到达终点，如果能就输出耗费时间，不能则输出Trapped!

分析：BFS裸题，只不过现在是在三维里面，可以走六个方向。

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<utility>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f
#define maxn 35
#define Clear(x) memset(x,0,sizeof(x))
#define fup(i,a,b) for(int i=a;i<b;i++)
#define rfup(i,a,b) for(int i=a;i<=b;i++)
#define fdn(i,a,b) for(int i=a;i>b;i--)
#define rfdn(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
using namespace std;
const double pi=acos(-1.0);
int l,r,c;

char maze[maxn][maxn][maxn];
int vis[maxn][maxn][maxn];
int dir[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};

struct node
{
    int x,y,z,t;
};
node vs,ed;

queue<node>q;

void init()
{
    while(!q.empty()) q.pop();
    Clear(vis);
}

bool check(int x,int y,int z)
{
    if(x<0||x>=l||y<0||y>=r||z<0||z>=c) return false;
    if(maze[x][y][z]=='#'||vis[x][y][z]) return false;
    return true;
}

int BFS()
{
    node temp;
    q.push(vs);
    while(!q.empty()){
        node now = q.front();
        q.pop();
        if(now.x==ed.x&&now.y==ed.y&&now.z==ed.z) return now.t;
        for(int i=0;i<6;i++)
        {
            temp.x=now.x+dir[i][0];
            temp.y=now.y+dir[i][1];
            temp.z=now.z+dir[i][2];
            if(check(temp.x,temp.y,temp.z))
            {
                vis[temp.x][temp.y][temp.z]=1;
                temp.t=now.t+1;
                q.push(temp);
            }
        }
    }
    return -1;
}

int main()
{
    while(scanf("%d%d%d",&l,&r,&c)==3&&l&&r&&c)
    {
        init();
        for(int i=0;i<l;i++)
        {
            for(int j=0;j<r;j++)
            {
                scanf("%s",maze[i][j]);
                for(int k=0;k<c;k++)
                {
                    if(maze[i][j][k]=='S') vs.x=i,vs.y=j,vs.z=k,vs.t=0;
                    if(maze[i][j][k]=='E') ed.x=i,ed.y=j,ed.z=k;
                }
            }
        }
        int ans = BFS();
        if(ans==-1) printf("Trapped!\n");
        else printf("Escaped in %d minute(s).\n",ans);
    }
    return 0;
}