WUST 2050 三维迷宫(bfs)

骑猪看日落 2022-06-12 13:52 160阅读 0赞

## 2050: 三维迷宫 ##

Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld  
Submitted: 50 Accepted: 12  
\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

## Description ##

你现在处于一栋楼里的'S'的起始位置,'\#'是墙壁,'.'是路,'E'是重点,'U'的楼梯代表你可以上去一层,'D'的楼梯代表你可以下去一层(保证上去跟下去的地方不会是墙壁)。请你告诉我至少要多少步才能到达终点,当然有可能去不到重点,这时请输出"Trapped!"

## Input ##

输入一个L、N、M,L代表层数,N,代表每层的长,M代表每层的宽。接下来有L个N\*M的图形，代表从第1层到第L层的地图。保证 L,N,M均不大于50

## Output ##

输入最小要多少步才能到终点,如果出不去,请输出"Trapped!"。

## Sample Input ![copy.gif][]      ##

3 5 5
    S...U
    #####
    ..###
    ....U
    #####
    
    .....
    .####
    ..###
    D###U
    #####
    
    .....
    .####
    ..###
    ###E.
    #####
    
    1 3 3
    S.#
    ##E
    ###

## Sample Output ##

20
    Trapped!

## Author ##

ControlBear

\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

题解：

不是很难的一道bfs题，处理起来有点麻烦而已

代码：

#include<iostream>
    #include<stdio.h>
    #include<map>
    #include<algorithm>
    #include<math.h>
    #include<queue>
    #include<stack>
    #include<string>
    #include<cstring>
    using namespace std;
    char p[55][55][55];//存图
    int vis[55][55][55];//遍历数组
    int dirx[4]={0,0,-1,1};
    int diry[4]={1,-1,0,0};
    int l,n,m;
    int sc,sx,sy,ec,ex,ey;//存起始点坐标
    struct node
    {
        int c,x,y;
        int step;
    };
    queue<node>q;
    int main()
    {
        int i,j,k,tag,s;
        node now,next;
        while(scanf("%d%d%d",&l,&n,&m)!=EOF)
        {
            while(!q.empty())q.pop();
            for(i=0;i<l;i++)
            {
                for(j=0;j<n;j++)
                    memset(vis[i][j],0,sizeof(vis[0][0][0])*(m+1));//初始化
            }
            for(i=0;i<l;i++)
            {
                for(j=0;j<n;j++)
                {
                    scanf("%s",p[i][j]);
                    for(k=0;k<m;k++)
                    {
                        if(p[i][j][k]=='S')
                        {
                            sx=j;
                            sy=k;
                            sc=i;
                        }
                        else if(p[i][j][k]=='E')
                        {
                            ex=j;
                            ey=k;
                            ec=i;
                        }
                    }
                }
            }
            now.c=sc,now.step=0,now.x=sx,now.y=sy;
            tag=0;
            q.push(now);
            vis[sc][sx][sy]=1;
            while(!q.empty())//日常宽搜
            {
                now=q.front();
                q.pop();
                if(now.c==ec&&now.x==ex&&now.y==ey)
                {
                    s=now.step;
                    tag=1;
                    break;
                }
                if(p[now.c][now.x][now.y]=='D')
                {
                    if(now.c-1>=0&&!vis[now.c-1][now.x][now.y])
                    {
                        vis[now.c-1][now.x][now.y]=1;
                        next=now;
                        next.c--;
                        next.step++;
                        q.push(next);
                    }
                }
                else if(p[now.c][now.x][now.y]=='U')
                {
                    if(now.c+1<l&&!vis[now.c+1][now.x][now.y])
                    {
                        vis[now.c+1][now.x][now.y]=1;
                        next=now;
                        next.c++;
                        next.step++;
                        q.push(next);
                    }
                }
                for(i=0;i<4;i++)
                {
                    int xx=dirx[i]+now.x;
                    int yy=diry[i]+now.y;
                    if(xx>=0&&xx<n&&yy>=0&&yy<m&&!vis[now.c][xx][yy]&&p[now.c][xx][yy]!='#')
                    {
                        vis[now.c][xx][yy]=1;
                        next.x=xx;
                        next.y=yy;
                        next.c=now.c;
                        next.step=now.step+1;
                        q.push(next);
                    }
                }
            }
            if(tag)
                printf("%d\n",s);
            else
                printf("Trapped!\n");
        }
        return 0;
    }

[Submit]: http://acm.wust.edu.cn/submitpage.php?id=2050&soj=0
[Status]: http://acm.wust.edu.cn/problemstatus.php?id=2050&soj=0
[Web Board]: http://acm.wust.edu.cn/bbs.php?pid=2050&soj=0
[copy.gif]: http://acm.wust.edu.cn/image/copy.gif