返回题解分享
讨论 / 题解分享/ 帖子详情

奇怪的电梯

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int N, A, B;
vector<int> K;
vector<bool> visited;
int min_steps = INT_MAX; // 记录全局最优解

void dfs(int current_floor, int steps) {
// 1. 剪枝:如果当前步数已经超过已知最优解,没必要继续
if (steps >= min_steps) {
return;
}

// 2. 结束条件:到达目标
if (current_floor == B) {
min_steps = min(min_steps, steps);
return;
}

// 3. 获取当前楼层的“魔力数字”
int step_size = K[current_floor];

// 如果当前楼层数字为0,无法移动,死胡同
if (step_size == 0) return;

// --- 尝试上升 ---
int next_up = current_floor + step_size;
if (next_up <= N && !visited[next_up]) {
visited[next_up] = true; // 标记
dfs(next_up, steps + 1);
visited[next_up] = false; // 回溯:撤销标记,以便其他路径可能用到它
}

// --- 尝试下降 ---
int next_down = current_floor - step_size;
if (next_down >= 1 && !visited[next_down]) {
visited[next_down] = true; // 标记
dfs(next_down, steps + 1);
visited[next_down] = false; // 回溯
}
}

int main() {
// 输入
cin >> N >> A >> B;
K.resize(N + 1); // 1-based indexing
for (int i = 1; i <= N; i++) {
cin >> K[i];
}

// 初始化
visited.resize(N + 1, false);
visited[A] = true; // 标记起点已访问

// 开始搜索
dfs(A, 0);

// 输出
if (min_steps == INT_MAX) {
cout << -1 << endl;
} else {
cout << min_steps << endl;
}

return 0;
}
1 回复 0 转发 0 喜欢 6 阅读
回复 (1)
默认 最新
露米 4 天前
看到你写的代码了,思路很清晰呢。

你用了 DFS 配合回溯,并且还细心地加上了 steps >= min_steps 的剪枝处理,这在搜索题目里是个非常棒的习惯,能帮程序省掉不少多余的计算。

这种“寻找最短路径”的问题,如果以后你想尝试不同的解法,也可以看看广度优先搜索(BFS)的思路,它在处理这类不带权重的最短步数问题时会非常自然。

目前的逻辑已经写得很完整了,运行起来还顺利吗?如果遇到了卡住的测试用例,我们可以再一起看看。 🙂
另外,在这个题目里,由于每一步的“代价”都是 1,所以 BFS 往往能更快地锁定答案。如果你以后对图论或者搜索算法的效率优化感兴趣,我们可以往那个方向再聊聊。

加油,期待看到你的更多分享。
0