南极亚拉 2017-08-04 05:48 采纳率: 0%
浏览 1012

POJ 2251 Dungeon Master(搜索)不知道为什么会超内存,求看看

我的思路是每次入队之后,把该位置设置为墙,所以就没有用vis数组。
把边界都设置为墙,所以可以不用考虑边界。
然后正常BFS走一遍。
结果 the memory limited 了

#include
#include
#include
#include
#include

#define MAX_N 32

using namespace std;
char map[MAX_N][MAX_N][MAX_N];
int L, R, C;

struct pos
{
int l;
int r;
int c;
int t;
};

int main()
{

while (cin >> L >> R >> C)
{
    queue<pos>q1;
    pos t;
    if (L == 0 && R == 0 && C == 0)break;
    memset(map, '#', sizeof(map));
    for (int i = 1; i <= L; i++)
    {
        for (int j = 1; j <= R; j++)
        {
            for (int k = 1; k <= C; k++)
            {
                cin >> map[i][j][k];
                if (map[i][j][k] == 'S')
                {
                    t.l = i;
                    t.r = j;
                    t.c = k;
                    t.t = 0;
                    q1.push(t);
                    map[i][j][k] = '#';
                }
            }
        }
    }
    int flag = 0;
    int ans = 0;
    while (!q1.empty())
    {   
        pos temp1 = q1.front();
        if (map[temp1.l][temp1.r][temp1.c] == 'E') { flag = 1; ans = q1.front().t; break; }

        map[temp1.l][temp1.r][temp1.c] = '#';
        q1.pop();
        temp1.t++;
        pos temp;
        if (temp1.c + 1 <= C) {
            if (map[temp1.l][temp1.r][temp1.c + 1] != '#')
            {
                temp = temp1;
                temp.c ++;

                q1.push(temp);
            }
        }
        if (temp1.c - 1 > 0) {
            if (map[temp1.l][temp1.r][temp1.c - 1] != '#')
            {
                temp = temp1;
                temp.c--;

                q1.push(temp);
            }
        }
        if (temp1.r + 1 <= R) {
            if (map[temp1.l][temp1.r + 1][temp1.c] != '#')
            {
                temp = temp1;
                temp.r++;

                q1.push(temp);
            }
        }
        if (temp1.r - 1 > 0) {
            if (map[temp1.l][temp1.r - 1][temp1.c] != '#')
            {
                temp = temp1;
                temp.r--;

                q1.push(temp);
            }
        }
        if (temp1.l + 1 <= L) {
            if (map[temp1.l + 1][temp1.r][temp1.c] != '#')
            {
                temp = temp1;
                temp.l++;

                q1.push(temp);
            }
        }
        if (temp1.l - 1 > 0) {
            if (map[temp1.l - 1][temp1.r + 1][temp1.c] != '#')
            {
                temp = temp1;
                temp.l--;

                q1.push(temp);
            }
        }

    }

    if (flag == 0)
    {
        cout << "Trapped!" << endl;
    }
    else cout << "Escaped in " << ans << " minute(s)." << endl;


}
return 0;

}

  • 写回答

1条回答 默认 最新

  • shen_wei 2017-08-04 06:20
    关注
    评论

报告相同问题?

悬赏问题

  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名