奇怪的电梯

attack

发布于 2018-04-12 07:36:15

1.6K00

代码可运行

文章被收录于专栏：数据结构与算法数据结构与算法

运行总次数：0

代码可运行

§、奇怪的电梯(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 }