ZOJ 1940 Dungeon Master【三维BFS】

题目大意：

在一个立体迷宫中，问你从起点走到终点的最少步数。

解题分析:

与普通的BFS基本类似，只需要给数组多加一维，并且走的时候多加上、下这两个方向就行。

#include <cstdio>

#include <cstring>

#include <queue>

#include <iostream>

#include <algorithm>

using namespace std;

int a,b,c;

char mpa[][][];

int vis[][][];

int dir[][]={{,,},{-,,},{,,},{,,},{,-,},{,,-}};

struct node{

    int x,y,z;

    int step;

    node(int a=,int b=,int c=,int d=){

        x=a,y=b,z=c,step=d;

    }

}st,et;

void bfs(){

    memset(vis,,sizeof(vis));

    queue<node>q;

    q.push(st);

    vis[st.x][st.y][st.z]=;

    while(!q.empty()){

        node now=q.front();

        q.pop();

        if(now.x==et.x&&now.y==et.y&&now.z==et.z){

            printf("Escaped in %d minute(s).\n",now.step);

            return;

        }

        for(int i=;i<;i++){

            int xx=now.x+dir[i][];

            int yy=now.y+dir[i][];

            int zz=now.z+dir[i][];

            if(xx<||xx>a||yy<||yy>b||zz<||zz>c||vis[xx][yy][zz]||mpa[xx][yy][zz]=='#')continue;

            vis[xx][yy][zz]=;

            q.push(node(xx,yy,zz,now.step+));

        }

    }

    printf("Trapped!\n");

}

int main(){

    while(scanf("%d %d %d",&a,&b,&c)!=EOF,a||b||c){

        for(int i=;i<=a;i++){

            getchar();

            for(int j=;j<=b;j++){

                scanf("%s",mpa[i][j]+);

                for(int k=;k<=c;k++){

                    if(mpa[i][j][k]=='S')st=node(i,j,k,);

                    if(mpa[i][j][k]=='E')et=node(i,j,k,);

                }

            }

        }

        bfs();

    }

    return ;

}

2018-08-30