奇怪的电梯——DFS算法

题目

题解

每到一层楼都面临了两种选择：上照旧下？因此我们可以定义一个布尔数组用来记载选择。
停止条件着实也显着，要么到了B层，要么没有找到楼层。
如果找到了，选择一个步调少的方式。又怎么体现没有找到楼层？
定义一个答案res，把它定义很大，如果找到了答案，更新最小值即可。
int res=1e9;
res = min(res,cnt);
这着实都很简朴，关键在于怎么剪枝？
第一，找答案的过程中如果发现cnt>res，就可以剪掉了
第二，每一层尽大概只来一次，如果选择了雷同的选择。就斲丧了肯定的cnt，不可取。如果选择了差异的方式，没找到B层也还行，如果找到了，那我们第一次到这个楼层的时候就该选这个差异的方式，整个方案就已经没有须要再举行下去了。所以综上，再选择的时候我们应该一个楼层最多走一次。
答案

2. #include <bits/stdc++.h>
4. using namespace std;
6. const int N = 210;
8. int n;
9. int A,B;
10. int K[N];
11. int res = 1e9;
12. bool st[N] = {false};
14. void dfs(int x,int cnt)
15. {
16.         if(cnt > res) return ;
17.         if(x == B)
18.         {
19.                 res = min(res,cnt);
20.                 return ;
21.         }
22.        
23.         if(x+K[x] <= n && !st[x+K[x]]){
24.                 st[x] = true;
25.                 dfs(x+K[x],cnt+1);
26.                 st[x]=false;
27.         }
28.         if(x-K[x] > 0 && !st[x+K[x]])
29.         {
30.                 st[x] = true;
31.                 dfs(x-K[x],cnt+1);
32.                 st[x] = false;
33.         }
34.        
35. }
37. int main()
38. {
39.         cin >> n >> A >> B;
40.         for(int i = 1;i<=n;i++)
41.         {
42.                 cin >> K[i];
43.         }
44.        
45.         st[A]=true;
46.         dfs(A,0);
47.         if(res == 1e9){
48.                 cout << "-1";
49.                 return 0;
50.         }
51.         cout << res;
52.         return 0;
53. }

复制代码