奇怪的电梯

2018-06-17 22:57:26来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

§、奇怪的电梯(lift.cpp)
§【问题描述】
§大楼的每一层楼都可以停电梯,而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如:3 3 1 2 5代表了Ki(K1=3,K2=3,……),从一楼开始。在一楼,按“上”可以到4楼,按“下”是不起作用的,因为没有-2楼。那么,从A楼到B楼至少要按几次按钮呢?
§【输入格式】lift.in
§输入文件共有二行,第一行为三个用空格隔开的正整数,表示N,A,B(1≤N≤200, 1≤A,B≤N),第二行为N个用空格隔开的正整数,表示Ki。
§【输出格式】lift.out
§输出文件仅一行,即最少按键次数,若无法到达,则输出-1。
§【输入样例】
§5 1 5
§3 3 1 2 5
§【输出样例】
§3
 1 #include<iostream>
 2 using namespace std;
 3 int lc[1000001];
 4 int tot=10001;
 5 int n;
 6 int beginn;
 7 int endn;
 8 int vis[1001];
 9 void dfs(int now,int step)
10 {
11     if(step>tot)
12     return;
13     if(now==endn)
14     {
15         if(step<tot)
16         tot=step;
17         return;
18     }
19     else
20     {
21         vis[now]=1;
22         if(now-lc[now]>0&&vis[now-lc[now]]==0)
23         {
24             dfs(now-lc[now],step+1);
25         }
26         if(now+lc[now]<=n&&vis[now+lc[now]]==0)
27         {
28             dfs(now+lc[now],step+1);
29         }
30         vis[now]=0;
31     }
32 }
33 int main()
34 {
35     
36     cin>>n>>beginn>>endn;
37     for(int i=1;i<=n;i++)
38     {
39         cin>>lc[i];
40     }
41     dfs(beginn,0);
42     if(tot!=10001)
43     cout<<tot;
44     else 
45     {
46         cout<<-1;
47     }
48     return 0;
49 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:创建和使用动态链接库、静态链接库 (C++)

下一篇:四则运算-单元测试