HDU2102A计划（BFS）

最新推荐文章于 2019-10-24 12:16:56 发布

小胡同的诗

最新推荐文章于 2019-10-24 12:16:56 发布

阅读量206

点赞数

分类专栏： BFS

本文链接：https://blog.csdn.net/calculate23/article/details/79316898

版权

BFS 专栏收录该内容

20 篇文章

订阅专栏

本文介绍了一个基于迷宫逃脱的游戏场景实现思路，利用BFS（宽度优先搜索）算法来判断玩家是否能在限定时间内成功逃脱。代码使用C++编写，并通过特定的数据结构和条件判断避免了无限循环的问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

传送门：点击打开链接

解题思路：两层，#表示楼梯，然后基本的bfs，注意特殊的这些情况，两层的同一个位置都是楼梯，会进入无限循环导致TLE。下楼或上楼撞墙死的也要筛掉。bfs或dfs都可以，图不大建议bfs吧快点，bfs0ms，不过oj不怎么稳定有时候会15ms

AC代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

struct node
{
    int x,y,z,time;
};

char map[2][12][12];
int book[2][12][12],n,m,T,nex[4][2]={0,1,1,0,0,-1,-1,0};
queue<node> que;

bool judge(int x,int y)
{
    if(x<0||x>=n||y<0||y>=m)
        return true;
    return false;
}

bool bfs(int x,int y,int z)
{
    node now,xia;
    int i;
    while(!que.empty())
        que.pop();
    now.x=x;
    now.y=y;
    now.z=z;
    now.time=0;
    que.push(now);
    while(!que.empty())
    {
        now=que.front();
        que.pop();
        for(i=0;i<4;i++)
        {
            xia.x=now.x+nex[i][0];
            xia.y=now.y+nex[i][1];
            xia.z=now.z;
            xia.time=now.time+1;
            if(xia.time>T || judge(xia.x,xia.y) || map[xia.z][xia.x][xia.y]=='*' || book[xia.z][xia.x][xia.y])
                continue;
            if(map[xia.z][xia.x][xia.y]=='#')
            {
                xia.z=!xia.z;
                if(map[xia.z][xia.x][xia.y]=='*' || map[xia.z][xia.x][xia.y]=='#')
                    continue;
            }
            if(map[xia.z][xia.x][xia.y]=='P')
                return false;
            book[xia.z][xia.x][xia.y]=1;
            que.push(xia);
        }
    }
    return true;
}

int main()
{
    int t,i,j,k,Sx,Sy,Sz;
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>T;
        memset(book,0,sizeof(book));
        for(i=0;i<2;i++)
        {
            getchar();
            for(j=0;j<n;j++)
                scanf("%s",map[i][j]);
            getchar();
        }
          for(i=0;i<2;i++)
        for(j=0;j<n;j++)
        for(k=0;k<m;k++)
        if(map[i][j][k]=='S')
            Sx=j,Sy=k,Sz=i;
        if(bfs(Sx,Sy,Sz))
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}