奇怪的电梯 c++ 深搜
时间: 2024-06-13 12:04:26 浏览: 9
这道题是一道深度优先搜索(DFS)的题目,需要从起点开始,不断地按照电梯的规则向上或向下移动,直到到达终点。在搜索的过程中,需要记录当前所在的楼层和已经按下的按钮次数,并且需要判断当前楼层是否已经被搜索过,以避免重复搜索。如果到达终点,则更新最少按键次数的值。最后输出最少按键次数即可。
参考代码如下(C++):
```
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
int n, a, b;
int k[N];
int cnt = 0x7fffffff; // int 的最大值
void dfs(int step, int sum)
{
if (step == b) cnt = min(cnt, sum); // 到达终点,更新最少按键次数
if (sum > cnt) return; // 如果当前按键次数已经大于最少按键次数,直接返回
if (step + k[step] <= n) dfs(step + k[step], sum + 1); // 向上移动
if (step - k[step] >= 1) dfs(step - k[step], sum + 1); // 向下移动
}
int main()
{
scanf("%d%d%d", &n, &a, &b);
for (int i = 1; i <= n; i++) scanf("%d", &k[i]);
dfs(a, 0);
if (cnt == 0x7fffffff) puts("-1"); // 无法到达终点
else printf("%d\n", cnt);
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)