C++ BFS Dungeon Master

Question

原题在这

代码

#include<iostream>
#include<cstdio>
using namespace std;
int map[501][501][501],T=1,W,X,Y,Z;
int F[6][3]={{0,0,1},{0,0,-1},{0,-1,0},{0,1,0},{1,0,0},{-1,0,0}};
struct node{
    int x,y,z,l;
}Q[1000001],S,E;
char c;
int BFS()
{
    W++;
    Q[W]=S;
    while(T<=W)
    {
        S=Q[T];
        T++;
        S.l++;
        for(int i=0;i<6;i++)
        {
            S.x+=F[i][0];
            S.y+=F[i][1];
            S.z+=F[i][2];
            if(S.x==E.x && S.y==E.y && S.z==E.z)
            {
                return S.l;
            }
            if(S.x>=0 && S.x<X && S.y>=0 && S.y<Y && S.z>=0 && S.z<Z && map[S.x][S.y][S.z]==0)
            {
                map[S.x][S.y][S.z]=1;
                W++;
                Q[W]=S;
            }
            S.x-=F[i][0];
            S.y-=F[i][1];
            S.z-=F[i][2];
        }
    }
    return -1;
}
int main()
{
    
    while(true)
    {
        cin>>X>>Y>>Z;
        if(X==0)
        {
            break;
        }
        for(int i=0;i<X;i++)
        {
            for(int j=0;j<Y;j++)
            {
                for(int k=0;k<Z;k++)
                {
                    cin>>c;
                    if(c!='#')
                    {
                        map[i][j][k]=0;
                    }
                    else
                    {
                        map[i][j][k]=1;
                    }
                    if(c=='S')
                    {
                        S.x=i;
                        S.y=j;
                        S.z=k;
                    }
                    if(c=='E')
                    {
                        E.x=i;
                        E.y=j;
                        E.z=k;
                    }
                }
            }
        }
        int num=BFS();
        if(num==-1) cout<<"Trapped!"<<endl;
        else cout<<"Escaped in "<<num<<" minute(s)."<<endl;
    }
}

##错误原因

除 一号 and 三号 测试点 外均未通过

Answer 1

根据您提供的代码和错误信息，我猜测可能是因为没有正确处理边界条件导致的。在进行 BFS 时，需要注意判断越界的情况，并在边界外提前停止搜索。

另外，这道题也需要注意初始化的问题。您在第一个 while 循环中已经将 T 和 W 的值都赋值为 1 了，但在下一个 while 循环中，T 又被赋值为 1。这可能会导致无法正常进入循环，从而导致程序无法正常执行。建议您在第二个 while 循环中将 T 的值赋为 1 后再进行判断。