POJ：Dungeon Master（BFS模板题）

原题链接

思路：

正常的思路，只不过是将二维BFS换成三维的，也算是个模板题吧（PS：DFS超容易超时）

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
char chart[40][40][40];

int then[6][3] = { {-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,1},{0,0,-1} };
int l, r, c;
int el, er, ec, sl, sr, sc;
int ans;
struct node
{
    int step;
    int l;
    int r;
    int c;
};
bool judge(int x, int y, int z)
{
    if (x >= 0 && x < l && y >= 0 && y < r && z >= 0 && z < c && chart[x][y][z] != '#')
        return true;
    else
        return false;
}
void bfs()
{
    int flag = 0;
    queue<node> q;
    node t;
    t.step = 0;
    t.l = sl;
    t.r = sr;
    t.c = sc;
    q.push(t);
    chart[sl][sr][sc] = '#';
    while (!q.empty())
    {
        int x, y, z;
        x = q.front().l;
        y = q.front().r;
        z = q.front().c;
        for (int i = 0; i < 6; i++)
        {
            int xx = x + then[i][0];
            int yy = y + then[i][1];
            int zz = z + then[i][2];
            if (judge(xx, yy, zz))
            {
                if (xx == el && yy == er && zz == ec)//在找到的时候就退出，如果在走到的时候再退出的话，会t
                {
                    ans = q.front().step + 1;
                    return;
                }
                node temp;
                temp.step = q.front().step + 1;
                temp.l = xx;
                temp.r = yy;
                temp.c = zz;
                chart[xx][yy][zz] = '#';
                q.push(temp);
            }
        }
        q.pop();
    }
    ans = -1;
}
int main()
{
    while (scanf("%d%d%d", &l, &r, &c))
    {
        if (l == 0 && r == 0 && c == 0)
            break;

        for (int i = 0; i < l; i++)
        {
            for (int j = 0; j < r; j++)
            {
                scanf("%s", chart[i][j]);
                for (int k = 0; k < c; k++)
                {
                    if (chart[i][j][k] == 'S')
                    {
                        sl = i;
                        sr = j;
                        sc = k;
                    }
                    if (chart[i][j][k] == 'E')
                    {
                        el = i;
                        er = j;
                        ec = k;
                    }
                }
            }
        }
        bfs();
        if (ans == -1)
            printf("Trapped!
");
        else
            printf("Escaped in %d minute(s).
", ans);
    }

    return 0;
}