C++-电梯 解题思路
2022/4/9 22:19:12
本文主要是介绍C++-电梯 解题思路,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
【Horn Studio】编程专栏: 电梯 解题思路
题目
题目描述
小明所住的居民楼的电梯非常独特,楼房的每一层都可以停电梯,并且第i(1≤i≤N)i(1≤i≤N)层的电梯上有一个数字Ki(0≤Ki≤N)Ki(0≤Ki≤N)。电梯上只有两个按钮:上、下。如果在第ii层按上,那么电梯会去到i+Kii+Ki楼(当然i+Kii+Ki必须要小于等于NN,否则电梯不会动);如果在ii层按下,那么电梯会去到i−Kii−Ki楼(当然i−Kii−Ki必须要大于等于11,否则电梯不会动);当然你也可以选择不按按钮。那么从AA层到BB层最少要按几次按钮呢?输入
第一行三个数字表示N,A,BN,A,B。第二行NN个数字,第ii个数字表示KiKi。
输出
一行,即最少按键次数,若无法到达,则输出−1−1。样例输入 复制
5 1 5 3 3 1 2 5
样例输出 复制
3
提示
所有数据满足:1≤N≤200,1≤A,B≤N1≤N≤200,1≤A,B≤N。思路
一道比较好的搜索题,dfs的话要略微剪枝,bfs应该就不用担心了
(我才不会告诉你bfs写不出来呢)
然而题目还是比较简单
可是我感觉自己的智商余额已经为0了
因此,我们就使用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 }
彩蛋
洛谷老黄历逼得我关了电脑……额……我用手机写博客!
这篇关于C++-电梯 解题思路的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升