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个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问