POJ 2251 Dungeon Master（广搜，三维，简单）

题目

简单的3d广搜，做法类似与 hdu 的 胜利大逃亡

#define  _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 32
char map[MAXN][MAXN][MAXN];
int a,b,c;
bool vis[MAXN][MAXN][MAXN];
struct tt
{
    int x,y,z,step;
};
queue<tt>q;
int xx[6]={0,0,1,-1,0,0};
int yy[6]={1,-1,0,0,0,0};
int zz[6]={0,0,0,0,1,-1};
int bfs(int sx,int sy,int sz,int ex,int ey,int ez)
{
    if(a==1&&b==1&&c==1)return 0;
    while(!q.empty())
        q.pop();
    memset(vis,false,sizeof(vis));
    tt front,rear,temp;
    front.x=sx;front.y=sy;front.z=sz;front.step=0;
    q.push(front);
    vis[sx][sy][sz]=true;
    while(!q.empty())
    {
        temp=q.front();
        q.pop();
        if(temp.x==ex&&temp.y==ey&&temp.z==ez)
            return temp.step;//原来是这个放错地方了，应该对出栈的数据进行检验
        for(int i=0;i<6;i++)
        {
            rear.x=temp.x+xx[i];
            rear.y=temp.y+yy[i];
            rear.z=temp.z+zz[i];
            rear.step=temp.step+1;
            if(rear.x>=0&&rear.x<a&&rear.y>=0&&rear.y<b&&rear.z>=0&&rear.z<c&&map[rear.x][rear.y][rear.z]!='#'&&vis[rear.x][rear.y][rear.z]==false)
            {
                q.push(rear);
                vis[rear.x][rear.y][rear.z]=true;
            }
        }
    }
    return 0;
}

int main()
{
    int i,j,k,ans,ex,ey,ez,sx,sy,sz;
    while(scanf("%d%d%d",&a,&b,&c)!=EOF)
    {
        if(a==0&&b==0&&c==0)break;
        for(i=0;i<a;i++)
        {
            for(j=0;j<b;j++)
            {
                scanf("%s",map[i][j]);  
                for(k=0;k<c;k++)
                {      
                    if(map[i][j][k]=='S')
                        sx=i,sy=j,sz=k;
                    if(map[i][j][k]=='E')
                        ex=i,ey=j,ez=k;
                }
            }
        }
        ans=bfs(sx,sy,sz,ex,ey,ez);
        if(ans==0)
            printf("Trapped!
");
        else
            printf("Escaped in %d minute(s).
",ans);
    }
    return 0;
}