算法1

参考文献

没有太多想讲的，主要就是简单的三维bfs，但是要注意的是边界条件要先写 if(x<0||x>=L||y<0||y>=R||z<0||z>=C) continue;不然se呜呜。找了半个小时的bug。

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=110;
char g[N][N][N];
int  dist[N][N][N];
struct Point{
    int x, y, z;
};
Point q[N*N*N];
int L,R,C;
int dx[]={1,-1,0,0,0,0};
int  dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};
int bfs(Point start,Point end)
{
    queue<Point>q;
    q.push(start);
    memset(dist,-1,sizeof dist);
    dist[start.x][start.y][start.z]=0;
    while(q.size())
    {
    Point t=q.front();
    q.pop();
    for(int i=0;i<6;i++){

        int x=t.x+dx[i],y=t.y+dy[i],z=t.z+dz[i];
              // 找了1个小时的se，原来这个边界条件要先写
        if(x<0||x>=L||y<0||y>=R||z<0||z>=C) continue;
        if(g[x][y][z]=='#') continue;
        if(dist[x][y][z]!=-1) continue;

        dist[x][y][z]=dist[t.x][t.y][t.z]+1;
        if(x==end.x&&y==end.y&&z==end.z) return dist[x][y][z];
       q.push({x,y,z});
    }
    }
    return -1;
}
int main()
{
     while (scanf("%d%d%d", &L, &R, &C), L || R || C)
    {
        Point start, end;
        for (int i = 0; i < L; i ++ )
            for (int j = 0; j < R; j ++ )
            {
                scanf("%s", g[i][j]);
                for (int k = 0; k < C; k ++ )
                {
                    char c = g[i][j][k];
                    if (c == 'S') start = {i, j, k};
                    else if (c == 'E') end = {i, j, k};
                }
            }

        int distance = bfs(start, end);
        if (distance == -1) puts("Trapped!");
        else printf("Escaped in %d minute(s).\n", distance);
    }
    return 0;
}