电梯
2022/4/15 23:17:47
本文主要是介绍电梯,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
题目描述
小明所住的居民楼的电梯非常独特,楼房的每一层都可以停电梯,并且第i(1≤i≤N)层的电梯上有一个数字Ki(0≤Ki≤N)。电梯上只有两个按钮:上、下。如果在第i层按上,那么电梯会去到i+Ki楼(当然i+Ki必须要小于等于N,否则电梯不会动);如果在i层按下,那么电梯会去到i−Ki楼(当然i−Ki必须要大于等于1,否则电梯不会动);当然你也可以选择不按按钮。那么从A层到B层最少要按几次按钮呢?输入
第一行三个数字表示N,A,B。第二行N个数字,第i个数字表示Ki。
输出
一行,即最少按键次数,若无法到达,则输出−1。样例输入
5 1 5 3 3 1 2 5
样例输出
3
思路
题目还是比较简单
我们使用dfs来解答,很容易发现实际上就是找最短路,路径长度的值可以抽象为每次增加的操作数,即均为1。
代码
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 int n,a,b,ans=0x7ffffff; 5 int to[205]; 6 bool vis[205]; 7 void dfs(int now,int sum) 8 { 9 if(now==b) ans=min(ans,sum); 10 if(sum>ans) return; 11 vis[now]=1; 12 if(now+to[now]<=n&&!vis[now+to[now]]) dfs(now+to[now],sum+1); 13 if(now-to[now]>=1&&!vis[now-to[now]]) dfs(now-to[now],sum+1); 14 vis[now]=0; 15 } 16 int main() 17 { 18 scanf("%d%d%d",&n,&a,&b); 19 for(int i=1;i<=n;i++) scanf("%d",&to[i]); 20 vis[a]=1; 21 dfs(a,0); 22 if(ans!=0x7ffffff) printf("%d",ans); 23 else printf("-1"); 24 return 0; 25 }
这篇关于电梯的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?