学步园

这是一个在三维空间中找出口的最短路径问题，从出发点开始，广度优先遍历地图，记录到达各地所需的步数，然后，AC！

但要小心，别漏了外加一层墙，不然就WA了（不加的话最外一层判断能否外的时候怎么办，哈哈）。

#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

const int maxn = 30 + 10;

typedef struct Tnode        //定义结点数据类型
{
    int x;
    int y;
    int z;
}node;

int L, R, C;
char maze[maxn][maxn][maxn];        //输入的地图
int vis[maxn][maxn][maxn];      //记录到达地图中各点所需步数，同时可表示状态，初始值为-1

int dx[] = {-1, 1, 0,  0, 0,  0};       //行数偏移量
int dy[] = { 0, 0, 1, -1, 0,  0};       //列数偏移量
int dz[] = { 0, 0, 0,  0, 1, -1};       //层数偏移量

bool bfs(node n)        //广度优先遍历，主要记录每到一个点的步数
{
    int i;
    queue<node> qu;     //广度优先遍历中用到的队列
    qu.push(n);     //第一个元素入列
    vis[n.x][n.y][n.z] = 0;     //改其步数为0

    while(!qu.empty())
    {
        n = qu.front();
        qu.pop();
        node newnode;       //将要遍历到的结点
        for(i = 0; i < 6; i++)      //north, south, east, west, up, down 共6个方向进行遍历
        {
            newnode.x = n.x + dx[i];
            newnode.y = n.y + dy[i];
            newnode.z = n.z + dz[i];
            if(maze[newnode.x][newnode.y][newnode.z] == 'E')        //如果找到出口，返回1
            {
                vis[newnode.x][newnode.y][newnode.z] = vis[n.x][n.y][n.z] + 1;
                return 1;
            }
            else if(maze[newnode.x][newnode.y][newnode.z] == '.' && vis[newnode.x][newnode.y][newnode.z] == -1)     //如果不是出口但可走的话
            {
                qu.push(newnode);
                vis[newnode.x][newnode.y][newnode.z] = vis[n.x][n.y][n.z] + 1;
            }
        }
    }
    return 0;
}

int main()
{
    int i, j, k;
    node s, e;      //s为出发点，e为出口
    while(cin>>L>>R>>C)
    {
        if(L == 0 && R == 0 && C == 0)
            return 0;
        for(i = 1; i <= L; i++)
            for(j = 1; j <= R; j++)
                for(k = 1; k <= C; k++)
                {
                    cin>>maze[i][j][k];
                    if(maze[i][j][k] == 'S')        //输入的时候就记录出发点
                    {
                        s.x = i;
                        s.y = j;
                        s.z = k;
                    }
                    if(maze[i][j][k] == 'E')        //输入的时候就记录出口
                    {
                        e.x = i;
                        e.y = j;
                        e.z = k;
                    }
                }
        for(i = 0; i <= R+1; i++)       //外加一层墙
            for(j = 0; j <= C+1; j++)
            {
                maze[0][i][j] = '#';
                maze[L+1][i][j] = '#';
            }
        for(i = 0; i <= R+1; i++)       //外加一层墙
            for(j = 0; j <= L+1; j++)
            {
                maze[i][j][0] = '#';
                maze[i][j][C+1] = '#';
            }
        for(i = 0; i <= L+1; i++)       //外加一层墙
            for(j = 0; j <= C+1; j++)
            {
                maze[i][0][j] = '#';
                maze[i][R+1][j] = '#';
            }
            
        memset(vis, -1, sizeof(vis));       //初始化步数状态数组为-1
        
        if(bfs(s))
            cout<<"Escaped in "<<vis[e.x][e.y][e.z]<<" minute(s)."<<endl;
        else
            cout<<"Trapped!"<<endl;
    }
    return 0;
}