1.题目描述
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 i 层楼（1≤i≤N）上有一个数字 Ki（0≤Ki≤N）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： 3,3,1,2,5 代表了 Ki（K1=3，K2=3，……），从 1 楼开始。在 1 楼，按“上”可以到 4 楼，按“下”是不起作用的，因为没有 −2 楼。那么，从 A 楼到 B 楼至少要按几次按钮呢？
2.输入格式
共二行。
第一行为三个用空格隔开的正整数，表示 N,A,B（1≤N≤200，1≤A,B≤N）。
第二行为 N 个用空格隔开的非负整数，表示 Ki。
3.输出格式
一行，即最少按键次数，若无法到达，则输出 -1。
4.输入输出样例
5.说明
对于 100% 的数据，1≤N≤200，1≤A,B≤N，0≤Ki≤N。
本题共 16个测试点，前 15 个每个测试点 6 分，最后一个测试点 10 分。
思路：
模拟在一栋有 n 层楼的建筑中，从起始楼层 A 通过按电梯按钮（电梯每次移动的楼层数由数组 evlt 表示）到达目标楼层 B 的最少操作次数（按电梯按钮的次数）。如果无法到达目标楼层，则输出 -1。
代码示例：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10010;
int n, A, B;
int res = 1e9;//存方案数
int evlt[N];//存按电梯按钮后电梯上升或下降的楼层数
bool st[N];//存每层楼走没走过 为什么要这一步后面说明
//当前在x楼，按了cnt次电梯
void dfs(int x,int cnt)
{
if (cnt >= res) return;
if (x<0 || x>n) return;
if (x == B)
{
res = min(res, cnt);
return;
}
//上
if (x + evlt[x]<= n&& !st[x + evlt[x]])
{
st[x + evlt[x]] = true;
dfs(x + evlt[x],cnt+1);
st[x + evlt[x]] = false;//回溯
}
//下
if (x - evlt[x] > 0&&! st[x - evlt[x]])
{
st[x - evlt[x]] = true;
dfs(x - evlt[x],cnt+1);
st[x - evlt[x]] = false;//回溯
}
}
int main()
{
scanf_s("%d %d %d", &n, &A, &B);
for (int i = 1; i <= n; i++)
{
scanf_s("%d", &evlt[i]);
}
dfs(A,0);
if (res == 1e9)
{
printf("-1\n");
}
else
printf("%d", res);
return 0;
}
为什么要用bool st[N];？
- 避免重复访问
在深度优先搜索过程中，如果不进行标记，可能会出现重复访问同一楼层的情况。例如，从某一楼层向上移动到达一个新楼层后，后续搜索过程中可能又会从其他路径再次回到这个新楼层，然后继续进行相同的向上或向下移动操作，这样就会陷入无限循环的搜索路径中，导致搜索无法有效进行。
通过使用 st 数组来标记每层楼是否已走过，当准备访问某一楼层时，先检查该楼层对应的 st 数组元素值。如果值为 true，表示该楼层已经被走过，就不再对其进行进一步的搜索操作（如向上或向下移动电梯并继续递归搜索），从而避免了重复访问同一楼层，保证了搜索过程能够有序、有效地进行下去。 - 优化搜索效率
标记已访问过的楼层可以帮助减少不必要的搜索分支。因为在寻找从起始楼层到目标楼层的最少操作次数的过程中，重复访问已经走过的楼层通常不会带来更优的解（除非存在特殊的楼层状态变化情况，但在当前代码设定下一般不会）。
所以，通过及时排除这些已经访问过的楼层，能够缩小搜索空间，让搜索算法更快地聚焦在那些还未被探索过的、可能存在更优解的路径上，从而提高了搜索效率，使得代码能够更快速地找到从起始楼层到目标楼层的最少操作次数（如果存在的话）。