奇怪的电梯——DFS算法

题目

题解

每到一层楼都面临了两种选择：上还是下？因此我们可以定义一个布尔数组用来记录选择。

终止条件其实也明显，要么到了B层，要么没有找到楼层。

如果找到了，选择一个步骤少的方式。又怎么表示没有找到楼层？

定义一个答案res，把它定义很大，如果找到了答案，更新最小值即可。

int res=1e9;

res = min(res,cnt);

这其实都很简单，关键在于怎么剪枝？

第一，找答案的过程中如果发现cnt>res，就可以剪掉了

第二，每一层尽可能只来一次，如果选择了相同的选择。就消耗了一定的cnt，不可取。如果选择了不同的方式，没找到B层也还行，如果找到了，那我们第一次到这个楼层的时候就该选这个不同的方式，整个方案就已经没有必要再进行下去了。所以综上，再选择的时候我们应该一个楼层最多走一次。

答案

#include <bits/stdc++.h>using namespace std;const int N = 210;int n;
int A,B;
int K[N];
int res = 1e9;
bool st[N] = {false};void dfs(int x,int cnt)
{if(cnt > res) return ;if(x == B){res = min(res,cnt);return ;}if(x+K[x] <= n && !st[x+K[x]]){st[x] = true;dfs(x+K[x],cnt+1);st[x]=false;}if(x-K[x] > 0 && !st[x+K[x]]){st[x] = true;dfs(x-K[x],cnt+1);st[x] = false;}}int main()
{cin >> n >> A >> B;for(int i = 1;i<=n;i++){cin >> K[i];}st[A]=true;dfs(A,0);if(res == 1e9){cout << "-1";return 0;}cout << res;return 0;
}