题解 P2360 【地下城主】

二元长天笑 · 2017-06-26 14:07:48 · 题解

其实这是一道很纯的bfs，但是由于维度加了一维，内存可能会相应的加大，但是没有关系，还是按原来的套路走就好了，我这里用的是纯手工队列，然后发现内存并没有爆，所以小伙伴们放心的开吧。现在回到正题，三维的bfs对于二维的来说，只是多了一个z坐标，所以我们在增加子节点的时候给他多搜索一个方向，如下：

x1=x[head]+d3[i];
            y1=y[head]+d1[i];
            z1=z[head]+d2[i];

然后就跟二维的套路一样，判断是否走过和是否越界，都没有的话就入队，如下：

if(a[x1][y1][z1]&&x1>=1&&x1<=l&&y1>=1&&y1<=n&&z1>=1&&z1<=m)
            {
                tail++;
                a[x1][y1][z1]=0;
                x[tail]=x1;
                y[tail]=y1;
                z[tail]=z1;
                f[tail]=head;

f数组在这里用来统计步数。然后再判断是否到达，如下：

if(x1==en1&&y1==en2&&z1==en3)
                {
                    while(f[tail])  //这是一个“非递归”，用来找步数。
                    {
                        tail=f[tail];
                        sum++;
                    }
                    cout<<"Escaped in "<<sum<<" minute(s)."<<endl;
                    return 0;   //找到了就直接输出结束
                }
            }

如果一直没有找到，队首就会追上队尾，然后就结束循环，在最后再输出无法到达。

全部代码如下：

#include<iostream>
#include<string>
using namespace std;
string s;
int n,m,l,be1,be2,be3,en1,en2,en3,x[10001],y[10001],z[10001],d1[6]={1,-1,0,0,0,0},d2[6]={0,0,-1,1,0,0},d3[6]={0,0,0,0,1,-1},tail=1,head=0,x1,y1,z1,f[10001],sum;
bool a[31][31][31]={0};
int main()
{
    cin>>l>>n>>m;
    for(int i=1;i<=l;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>s;
            for(int k=0;k<m;k++)
            {
                if(s[k]=='.')
                    a[i][j][k+1]=1;
                if(s[k]=='S')
                {
                    be1=i;be2=j;be3=k+1;
                }
                if(s[k]=='E')
                {
                    en1=i;en2=j;en3=k+1;
                    a[i][j][k+1]=1;
                }
            }
        }
    x[tail]=be1,y[tail]=be2,z[tail]=be3;
    do
    {
        head++;
        for(int i=0;i<6;i++)
        {
            x1=x[head]+d3[i];
            y1=y[head]+d1[i];
            z1=z[head]+d2[i];
            if(a[x1][y1][z1]&&x1>=1&&x1<=l&&y1>=1&&y1<=n&&z1>=1&&z1<=m)
            {
                tail++;
                a[x1][y1][z1]=0;
                x[tail]=x1;
                y[tail]=y1;
                z[tail]=z1;
                f[tail]=head;
                if(x1==en1&&y1==en2&&z1==en3)
                {
                    while(f[tail])
                    {
                        tail=f[tail];
                        sum++;
                    }
                    cout<<"Escaped in "<<sum<<" minute(s)."<<endl;
                    return 0;
                }
            }
        }

    }while(head<tail);
    cout<<"Trapped!"<<endl;
}

还有一点要注意，那就是输入这个地牢的时候坐标特别容易弄错，大家三思而后行啊！