1096. 地牢大师(蓝桥杯/bfs宽搜求最小距离)

题目:

1096. 地牢大师 - AcWing题库

 

输入样例:
3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0
输出样例:
Escaped in 11 minute(s).
Trapped!

思路:bfs(三维)

代码:

 

#include<bits/stdc++.h>
using namespace std;
const int N=110;
char p[N][N][N];//三维空间某位置上的字符
int dist[N][N][N];//距离起点的距离
struct Point//坐标
{
    int x,y,z;
};

int L,R,C;

int bfs(Point Start,Point End)
{
    queue<Point>q;
    memset(dist,-1,sizeof dist);
    q.push(Start);
    dist[Start.x][Start.y][Start.z]=0;
    while(q.size()){
        Point t=q.front();
        q.pop();
        int dx[6]={1,-1,0,0,0,0},dy[6]={0,0,1,-1,0,0},dz[6]={0,0,0,0,1,-1};
        for(int i=0;i<6;i++){
            int x=t.x+dx[i],y=t.y+dy[i],z=t.z+dz[i];
            if(x < 0 || x >= L || y < 0 || y >= R || z < 0 || z >= C)continue;
            if(p[x][y][z]=='#')continue;
            if(dist[x][y][z]!=-1)continue;
            
            dist[x][y][z]=dist[t.x][t.y][t.z]+1;
            if(x==End.x&&y==End.y&&z==End.z)return dist[x][y][z];
            q.push({x,y,z});
        }
    }
    return -1;
}

int main()
{
    cin>>L>>R>>C;
    Point Start,End;
    while(scanf("%d%d%d",&L,&R,&C),L||R||C)//输入000停止
    {
        for(int i=0;i<L;i++){
            for(int j=0;j<R;j++){
                scanf("%s",&p[i][j]);//按行输入
                
                for(int k=0;k<C;k++){
                    if(p[i][j][k]=='S')Start={i,j,k};
                    else if(p[i][j][k]=='E')End={i,j,k};
                }
            }
        }
        int distance=bfs(Start,End);
        if(distance==-1)printf("Trapped!\n");
        else printf("Escaped in %d minute(s).\n",distance);
    }
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/270833.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Midjourney】Midjourney提示词格式详解

目录 &#x1f347;&#x1f347;Midjourney是什么&#xff1f; &#x1f349;&#x1f349;Midjourney怎么用&#xff1f; &#x1f514;&#x1f514;Midjourney提示词格式 &#x1f341; 1.模型版本提示词&#x1f341; 参数 参数详解 应用示例 &#x1f343; 2.风格…

AssertionError: The environment must specify an action space. 报错 引发的惨案

起因是&#xff1a;从github上下载了一个代码&#xff0c;运行出错。 整体流程&#xff1a; 1. AssertionError: The environment must specify an action space. 报错&#xff0c;解决方案是 降级gym到 gym0.18.0 2.为了降级gym gym0.18.0 报错&#xff0c;发现需要降级 setup…

Django-REST-Framework 如何快速生成Swagger, ReDoc格式的 REST API 文档

1、API 接口文档的几种规范格式 前后端分离项目中&#xff0c;使用规范、便捷的API接口文档工具&#xff0c;可以有效提高团队工作效率。 标准化的API文档的益处&#xff1a; 允许开发人员以交互式的方式查看、测试API接口&#xff0c;以方便使用将所有可暴露的API接口进行分…

【K8S 基本概念】Kurbernetes的架构和核心概念

目录 一、Kurbernetes 1.1 简介 1.2、K8S的特性&#xff1a; 1.3、docker和K8S&#xff1a; 1.4、K8S的作用&#xff1a; 1.5、K8S的特性&#xff1a; 二、K8S集群架构与组件&#xff1a; 三、K8S的核心组件&#xff1a; 一、master组件&#xff1a; 1、kube-apiserve…

JVM 类加载子系统

1. 前言 ​ 虚拟机就是一款用来执行虚拟计算机指令的计算机软件。它相当于一台虚拟计算机。大体上&#xff0c;虚拟机分为系统虚拟机和程序虚拟机。系统虚拟机就相当于一台物理电脑&#xff0c;里面可以安装操作系统&#xff1b;程序虚拟机是为了执行单个计算机程序而设计出来…

Python爬虫中的多线程、线程池

进程和线程的基本介绍 进程是一个资源单位&#xff0c;线程是一个执行单位&#xff0c;CPU调度线程来执行程序代码。 当运行一个程序时&#xff0c;会给这个程序分配一个内存空间&#xff0c;存放变量等各种信息资源&#xff0c;而这个内存空间可以说是一个进程&#xff0c; 一…

论文阅读<CF-YOLO: Cross Fusion YOLO for Object Detection in Adverse Weather.....>

论文链接&#xff1a;https://arxiv.org/pdf/2309.08152.pdfhttps://arxiv.org/pdf/2206.01381.pdfhttps://arxiv.org/pdf/2309.08152.pdf 代码链接&#xff1a;https://github.com/DiffPrompter/diff-prompter 目前没有完整代码放出。 恶劣天气下的目标检测主要有以下三种解…

2023年12月【考试战报】|ORACLE OCP 19C考试通过

2023年10月【考试战报】|ORACLE OCP 19C考试通过-CSDN博客文章浏览阅读122次。自OCP认证进入中国以来&#xff0c;越来越被大多数DBA所认可&#xff0c;也越来越被企业所重视&#xff0c;90%以上DBA深造&#xff0c;都会选择OCP认证。随着OCP认证在全国范围内的普及&#xff0c…

ios 之 数据库、地理位置、应用内跳转、推送、制作静态库、CoreData

第一节&#xff1a;数据库 常见的API SQLite提供了一系列的API函数&#xff0c;用于执行各种数据库相关的操作。以下是一些常用的SQLite API函数及其简要说明&#xff1a;1. sqlite3_initialize:- 初始化SQLite库。通常在开始使用SQLite之前调用&#xff0c;但如果没有调用&a…

【MySQL】数据库之存储引擎

目录 一、什么是存储引擎 MySQL 整个查询执行过程&#xff0c;即MySQL的工作原理&#xff1f; 二、MyISAM 与 InnoDB 的区别&#xff1f; 三、如何查看当前表的存储引擎&#xff1f; 1.查看当前的存储引擎 2.查看数据库支持哪些存储引擎 四、如何设置存储引擎&#xff1f;…

使用 Jekyll 构建你的网站 - 初入门

文章目录 一、Jekyll介绍二、Jekyll安装和启动2.1 配置Ruby环境1&#xff09;Windows2&#xff09;macOS 2.2 安装 Jekyll2.3 构建Jekyll项目2.4 启动 Jekyll 服务 三、Jekyll常用命令四、目录结构4.1 主要目录4.2 其他的约定目录 五、使用GitLink构建Jekyll博客5.1 生成Jekyll…

Github 2023-12-25开源项目周报 Top15

根据Github Trendings的统计&#xff0c;本周(2023-12-25统计)共有15个项目上榜。根据开发语言中项目的数量&#xff0c;汇总情况如下&#xff1a; 开发语言项目数量Python项目7Go项目2非开发语言项目2Dart项目1TypeScript项目1Rust项目1Kotlin项目1 GPT-Engineer: 自然语言编…

DevC++ easyx实现视口编辑,在超过屏幕大小的地图上画点,与解决刮刮乐bug效果中理解C语言指针的意义

继上篇文案&#xff0c; DevC easyx实现地图拖动&#xff0c;超过屏幕大小的巨大地图的局部显示在屏幕的方法——用悬浮窗的原理来的实现一个视口-CSDN博客 实现了大地图拖动&#xff0c;但是当时野心不止&#xff0c;就想着一气能搓啥就继续搓啥&#xff0c;看着地图移动都搓…

nodejs+vue+微信小程序+python+PHP基于Android的共享自习室APP系统-计算机毕业设计推荐

1.用户端&#xff1a; 一、首页&#xff1a; &#xff08;1&#xff09;店面轮播图及位置、营业时间 &#xff08;2&#xff09;预约储物柜功能&#xff1a;选择储物柜号码、确认预约 &#xff08;3&#xff09;会员功能&#xff1a;解锁VIP座位、个人积分信息&#xff08;查看…

STM32 cubeMX 光敏电阻AD转化实验

文章代码使用 HAL 库。 文章目录 前言一、光敏电阻介绍二、光敏电阻原理图解析三、ADC采样介绍1. 工作原理&#xff1a;2. ADC精度&#xff1a; 四、STM32 cubeMX配置ADC采样五、代码编写总结 前言 实验开发板&#xff1a;STM32F051K8。所需软件&#xff1a;keil5 &#xff0c;…

解决ELement-UI三级联动数据不回显

目录 一.处理数据时使用this.$set方法来动态地设置实例中的属性&#xff0c;以确保其响应式。 二.检查数据格式是否正确 三.绑定v-if 确保每次执行 四.完整代码 一.处理数据时使用this.$set方法来动态地设置实例中的属性&#xff0c;以确保其响应式。 二.检查数据格式是否正确…

TypeScript下载安装,编译运行

TypeScript是拥有类型的JavaScript超集&#xff0c;它可以编译成普通、干净、完整的JavaScript代码。 简单理解&#xff1a;TypeScript就是加强版的JavaScript。 TypeScript最终会被编译成JavaScript代码&#xff0c;那么我们必然需要对应的编译环境 环境搭建前提&#xff1a…

简单的喷淋实验(2):(1)根据土壤湿度自动控制喷淋开关;(2)根据光照强度控制风扇以及灯的开关---嵌入式实训

目录 简单的喷淋实验(2)&#xff1a; &#xff08;1&#xff09;根据土壤湿度自动控制喷淋开关&#xff1b; &#xff08;2&#xff09;根据光照强度控制风扇以及灯的开关---嵌入式实训 任务2&#xff1a; 具体过程&#xff1a; 所用的头文件&#xff1a; data_global.h …

人工智能_机器学习073_SVM支持向量机_人脸识别模型建模_预测可视化_网格搜索交叉验证最优化参数对比---人工智能工作笔记0113

接着上一节来说,可以看到我们已经找到了合适的参数,然后 我们可以看一下这里 gc.best_params_ 就可以打印出最合适的参数 然后我们把最合适串按说填入到代码中,然后进行计算,看看得分 可以看到得分,训练数据是1.0 然后测试数据得分是0.7857...对吧

nodejs+vue+微信小程序+python+PHP的热带野生动物园景点预约订票系统的设计与实现-计算机毕业设计推荐

管理员是系统的管理者&#xff0c;拥有系统的所有权限&#xff0c;通过系统设定的账号和密码登录后对系统进行管理&#xff0c;包括密码修改、用户管理。新闻公告的管理、景点管理、订单管理。管理员登录中&#xff0c;通过用户的登录名和密码到热带野生动物园景点预约订票系统…