C语言洛谷题目分享(9)奇怪的电梯

2024-04-16 01:12

本文主要是介绍C语言洛谷题目分享(9)奇怪的电梯,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1.前言

2.题目:奇怪的电梯

1.题目描述

2.输入格式

3.输出格式

4.输入输出样例

5.说明

6.题解

 3.小结


1.前言

哈喽大家好啊,前一段时间小编去备战蓝桥杯所以博客的更新就暂停了几天,今天继续为大家带来题解分享,希望大家多多支持我哦~

2.题目:奇怪的电梯

1.题目描述

呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第 i 层楼(1≤i≤N)上有一个数字 Ki​(0≤Ki​≤N)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如: 3,3,1,2,5 代表了 Ki​(K1​=3,K2​=3,……),从 1 楼开始。在 1 楼,按“上”可以到 4 楼,按“下”是不起作用的,因为没有 −2 楼。那么,从 A 楼到 B 楼至少要按几次按钮呢?

2.输入格式

共二行。

第一行为三个用空格隔开的正整数,表示 N,A,B(1≤N≤200,1≤A,B≤N)。

第二行为 N 个用空格隔开的非负整数,表示 Ki​。

3.输出格式

一行,即最少按键次数,若无法到达,则输出 -1

4.输入输出样例

5.说明

对于 100% 的数据,1≤N≤200,1≤A,B≤N,0≤Ki​≤N。

本题共 16个测试点,前 15 个每个测试点 6 分,最后一个测试点 10 分。

6.题解

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N=230;int n=0,a=0,b=0;//分别记录大楼总高度,当前楼层,目标楼层
int fl[N];//记录按钮
int ans=1e9;//记录次数
bool st[N];//判断该楼层是否已经登过void dfs(int x,int ans1){if(ans1>=ans)return ;if(x<0||x>n)return ;//超出范围了剪枝if(x==b){ans=min(ans,ans1);return ;}if(x+fl[x]<=n&&!st[x+fl[x]]){st[x+fl[x]]=true;dfs(x+fl[x],ans1+1);st[x+fl[x]]=false;//回溯原来状态}if(x+fl[x]>0&&!st[x+fl[x]]){st[x+fl[x]]=true;dfs(x-fl[x],ans1+1);st[x+fl[x]]=false;}
}int main(){cin>>n>>a>>b;for(int i=1;i<=n;i++){cin>>fl[i];}dfs(a,0);if(ans==1e9){printf("-1");return 0;}cout<<ans;return 0; 
}

这道题思路如下:

  •  这道题我是用dfs解决的。
  • 搜索有俩条路径:一个是向上查询,另一个是向下查询。
  • 剪枝条件有俩个:1.如果上升或下降小于等于0或者大于n。     2.枚举次数过大 。
  • 另外为了节省时间,选择用bool数组记录楼层选择状态,以免造成某一层楼反复到达所造成的tle。

 3.小结

今天的分享到这里就结束了,希望大家多多点赞,多多收藏,多多支持我哦~

这篇关于C语言洛谷题目分享(9)奇怪的电梯的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/907426

相关文章

C语言中位操作的实际应用举例

《C语言中位操作的实际应用举例》:本文主要介绍C语言中位操作的实际应用,总结了位操作的使用场景,并指出了需要注意的问题,如可读性、平台依赖性和溢出风险,文中通过代码介绍的非常详细,需要的朋友可以参... 目录1. 嵌入式系统与硬件寄存器操作2. 网络协议解析3. 图像处理与颜色编码4. 高效处理布尔标志集合

SpringBoot请求参数接收控制指南分享

《SpringBoot请求参数接收控制指南分享》:本文主要介绍SpringBoot请求参数接收控制指南,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring Boot 请求参数接收控制指南1. 概述2. 有注解时参数接收方式对比3. 无注解时接收参数默认位置

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum(枚举)是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚

Go 语言中的select语句详解及工作原理

《Go语言中的select语句详解及工作原理》在Go语言中,select语句是用于处理多个通道(channel)操作的一种控制结构,它类似于switch语句,本文给大家介绍Go语言中的select语... 目录Go 语言中的 select 是做什么的基本功能语法工作原理示例示例 1:监听多个通道示例 2:带

C语言函数递归实际应用举例详解

《C语言函数递归实际应用举例详解》程序调用自身的编程技巧称为递归,递归做为一种算法在程序设计语言中广泛应用,:本文主要介绍C语言函数递归实际应用举例的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录前言一、递归的概念与思想二、递归的限制条件 三、递归的实际应用举例(一)求 n 的阶乘(二)顺序打印

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时