P2360 地下城主

题目大意

背景是逃离(3D)地下监狱，也就是三维样例，你可以前往所在小格的前方，后方，左方，右方，上层，下层的小格,'.'表示可走，'x'表示墙壁，'S'表示起点，'E'表示终点。每走一小格花费一分钟时间，求逃离地下监狱需要的最少时间。（原题链接：P2360 地下城主）

输入格式:

第一行：(l)表示有多少层，(r)表示一层有多少行，(c)表示一行有多少个
接下来：(l)个矩阵，表示监狱的每一层

输出格式:

一个数：所要花费的最少时间
如果能成功逃离输出：“(Escaped) (in) (x) (minute(s))”，否则输出“(Trapped!)”

输入样例:

3 4 5
S....
.xxx.
.xx..
xxx.x

xxxxx
xxxxx
xx.xx
xx...

xxxxx
xxxxx
x.xxx
xxxxE

输出样例

Escaped in 11 minute(s).

思路：

这道题明显是使用(BFS)的，但是知道用(BFS)平时都是搜索那种两维的，这次是三维的怎么搞，第一想法是压缩成两维，可是真的太抽象了。。。
于是看了一下题解是说直接把数组改成三维就好了嘛，这样看来，这道题好水啊，，，
于是我显示用了三个数组

dx[4] = {-1, 0, 1, 0}
dy[4] = {0, 1, 0, -1}
dz[2] = {-1, 1};

然后我又是这样枚举的

for(int i = 0; i < 4; i++)
      for(int i = 0; i < 2; i++)
            int xx = t.x + dx[i], yy = t.y +dy[i], zz = t.z + dz[j];

然后就爆零了。。
为什么dist数组根本没有得到更新，调试了一下，发现，我们一次只能做一个动作（前后上下左右，不能直接右上右下这样走），因此发现了问题，把代码改成了这样。

dx[6] = {-1, 0, 1, 0, 0, 0}
dy[6] = {0, 1, 0, -1, 0, 0}
dz[6] = {0, 0, 0, 0, -1, 1};
for(int i = 0; i < 6; i++)
            int xx = t.x + dx[i], yy = t.y +dy[i], zz = t.z + dz[i];

顺利(AC)
第一次做三维(BFS),觉得挺典型的记录一下~

代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 35;
int l, r, c, bx, by, bz, ex, ey, ez; //l是一共几层 r是每层几行 c是每行几个
int dist[N][N][N];
int mp[N][N][N];
int dx[6] = {-1, 0, 1, 0, 0, 0}, dy[6] = {0, 1, 0, -1, 0, 0}, dz[6] = {0, 0, 0, 0, -1, 1};

struct node
{
    int x, y, z;
};

void bfs(int sx, int sy, int sz)
{
    memset(dist, -1, sizeof dist);
    queue<node> q;
    node start;
    start.x = sx, start.y = sy, start.z = sz;
    q.push(start);
    dist[sx][sy][sz] = 0;

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        for(int i = 0; i < 6; i++)
        {
            int xx = t.x + dx[i], yy = t.y +dy[i], zz = t.z + dz[i];
            if(zz >= 1 && zz <= l && xx >= 1 && xx <= r && yy >= 1 && yy <= c && dist[xx][yy][zz] == -1 && mp[xx][yy][zz] != -1)
            {
                dist[xx][yy][zz] = dist[t.x][t.y][t.z] + 1;
                node p;
                p.x = xx, p.y = yy, p.z = zz;
                q.push(p);
            }
            if(mp[xx][yy][zz] == 'E') return;
        }
    }
}

int main()
{
    cin >> l >> r >> c;
    for(int z = 1; z <= l; z++)
    {
        for(int x = 1; x <= r; x++)
        {
            for(int y = 1; y <= c; y++) 
            {
                char c;
                cin >> c;
                if(c == 'S') //起点
                {
                    mp[x][y][z] = 2;
                    bx = x, by = y, bz = z;
                }
                else if(c == '#') mp[x][y][z] = -1; //障碍
                else if(c == '.') mp[x][y][z] = 1; //可走
                else if(c == 'E') //终点
                {
                    mp[x][y][z] = 3;
                    ex = x, ey = y, ez = z;
                }   
            }
        }
    }
    
    bfs(bx, by, bz);

    if(dist[ex][ey][ez] == -1) cout << "Trapped!" << endl;
    else cout << "Escaped in " << dist[ex][ey][ez] << " minute(s)." << endl;

    return 0;
}