前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Dungeon Master POJ - 2251(bfs)

Dungeon Master POJ - 2251(bfs)

作者头像
_DIY
发布2019-09-11 17:26:24
3040
发布2019-09-11 17:26:24
举报

对于3维的,可以用结构体来储存,详细见下列代码。

样例可以过,不过能不能ac还不知道,疑似poj炸了,

代码语言:javascript
复制
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int INF = 0x3f3f3f3f;
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 bx, by, bz;
int ex, ey, ez;
const int maxn = 30 + 5;
class POS
{
    public:
        POS():x_(-1), y_(-1), z_(-1){ }
        POS(int x, int y, int z):x_(x), y_(y), z_(z){ }
        int getX(){ return x_;}
        int getY(){ return y_;}
        int getZ(){ return z_;}
    private:
        int x_, y_, z_;
};
typedef POS P;
struct Level
{
    char maze[maxn][maxn];
    int vis[maxn][maxn];
    int d[maxn][maxn];
};
int L, R, C;
Level *h;
bool op(int x, int y, int z)
{
    if(x >= 0 && x < R && y >= 0 && y < C && z >= 0 && z < L)
        return true;
    return false;
}
int bfs()
{
    queue<P> pos;
    pos.push(P(bx, by, bz));
    while(!pos.empty())
    {
        P p = pos.front();
        pos.pop();
        if(p.getX() == ex && p.getY() == ey && p.getZ() == ez)
            break;
        h[p.getZ()].vis[p.getX()][p.getY()] = 1;
        for(int i = 0; i < 6; i++)
        {
            int curx = p.getX() + dx[i], cury = p.getY() + dy[i], curz = p.getZ() + dz[i];
            if(op(curx, cury, curz) && h[curz].maze[curx][cury] != '#' && !h[curz].vis[curx][cury])
            {
                h[curz].vis[curx][cury] = 1;
                pos.push(P(curx, cury, curz));
                h[curz].d[curx][cury] = h[p.getZ()].d[p.getX()][p.getY()] + 1;
            }
        }

    }
    return h[ez].d[ex][ey];

}
int main()
{
    while(cin >> L >> R >> C && (L || R || C))
    {
        bx = by = bz = -1;
        ex = ey = ez = -1;
        h = new Level[L];
        for(int i = 0; i < L; i++)
        {
            for(int j = 0; j < R; j++)
            {
                scanf("%s", h[i].maze[j]);      //input
                for(int k = 0; k < C ; k++)
                {
                    h[i].vis[j][k] = 0;
                    if(h[i].maze[j][k] == 'S')
                    {
                        h[i].d[j][k] = 0;
                        bx = j;
                        by = k;
                        bz = i;
                    }
                    else
                        h[i].d[j][k] = INF;
                    if(h[i].maze[j][k] == 'E')
                    {
                        ex = j;
                        ey = k;
                        ez = i;
                    }
                }

            }

        }
        int ans = bfs();
        if(ans == INF)
            cout << "Trapped!" << endl;
        else
            cout << "Escaped in " << ans << " minute(s)." << endl;




        delete []h;

    }

}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-05-25 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档