【DFS】奇怪的电梯
2024-08-28 16:18:00
奇怪的电梯
题目描述
有一天桐桐做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第i层楼(1≤i≤N)上有一个数字K;(0≤Ki≤N)。电梯只有四 个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如:3 3 1 2 5代表了Ki (K1=3,K2=3,…),从一楼开始。在一楼,按“上,”可以到4楼,按“下”是不起作用的,因为没有-2楼。那么,从A楼到B楼至少要按几次按钮 呢?
输入
第1行为三个正整数,表示N,A,B(1≤N≤200,1≤A,B≤N);
第2行为N个正整数,表示Ki。
输出
1行,即最少按键次数,若无法到达,则输出-1。
样例输入
5 1 5
3 3 1 2 5
样例输出
3 DFS大水题,不说了
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
struct data{
int t,s;
}Que[2001];
bool vis[2001];
int a[2001];
int N,A,B;
void BFS(){
int l=1,r=1;
Que[r].s=0,Que[r].t=A;
vis[A]=true;
while(l<=r){
if(Que[l].t==B){
printf("%d\n",Que[l].s);
exit(0);
}
int num=Que[l].s,to=Que[l].t;
if(to-a[to]>=1&&!vis[to-a[to]]){
if(to-a[to]==B){
printf("%d\n",num+1);
exit(0);
}
vis[to-a[to]]=true;
Que[++r].s=num+1;
Que[r].t=to-a[to];
}
if(to+a[to]<=N&&!vis[to+a[to]]){
if(to+a[to]==B){
printf("%d\n",num+1);
exit(0);
}
vis[to+a[to]]=true;
Que[++r].s=num+1;
Que[r].t=to+a[to];
}
cout<<endl;
l++;
}
return ;
}
const int INF = 9999999;
int main(){
N=read(),A=read(),B=read();
for(int i=1;i<=N;i++) a[i]=read();
BFS();
printf("%d\n",-1);
return 0;
}
最新文章
- java使用websocket,并且获取HttpSession,源码分析
- MSSQLLocalDB 连接字符串 vs2015
- [LeetCode] Isomorphic Strings
- [问题2014A12] 复旦高等代数 I(14级)每周一题(第十四教学周)
- OpenGL es3.0 初始化及渲染
- homework-03 图形化化最大子序列和
- php文件上传大小限制的修改方法大全
- 使用SAE部署Flask,使用非SAE flask版本和第三方依赖包的方法
- bootstarp基本模板
- ORACLE Install (10g r2) FOR Red Hat Enterprise Linux Server release 5.5 (64 bit) (转)
- .NET 对象序列化和系列化德
- BZOJ 3729: Gty的游戏 [伪ETT 博弈论]【学习笔记】
- numpy用法归纳
- oracle expdp自动备份脚本
- SFTP远程连接服务器上传下载文件-vs2013项目实例
- Variables and Arithmetic Expression
- Starting MySQL ERROR! Couldn&#39;t find MySQL server (/usr/local/mysql/bin/mysqld_safe)
- jquery 获取元素(父节点,子节点,兄弟节点),元素筛选
- vue-cli引入jquery方法
- JavaScript--Dom间接选择器