#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;
}
#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 阅读



