P1135_牛客博客

P1135 奇怪的电梯

问题描述

有一栋 $N$ 层的高楼（ $1 \leq N \leq 200$ ），每层楼 $i$ 有一个数字 $K_i$ 。电梯在第 $i$ 层时，可以移动到：

$i + K_i$ 层（如果 $\leq N$ ）
$i - K_i$ 层（如果 $\geq 1$ ）

给定起点 $A$ 和终点 $B$ ，求从 $A$ 到 $B$ 的最少按键次数（每次移动算一次按键）。如果无法到达，输出 $-1$ 。

问题分析

每层楼是一个节点（共 $N$ 个节点），从节点 $i$ 到 $i+K_i$ 和 $i-K_i$ 有两条有向边（如果目标节点在 $[1, N]$ 范围内），所有边的权重为 1（每次移动消耗一次按键）
在无权图中求单源最短路径，起点： $A$ ，终点： $B$

算法选择：BFS（广度优先搜索）

为什么选 BFS？

最短路径保证：BFS 按层遍历，第一次到达 $B$ 时的路径长度就是最短路径
效率最优：时间复杂度 $O(N)$ ，空间复杂度 $O(N)$ ，完美匹配 $N \leq 200$ 的约束
天然防环：通过访问标记避免重复访问，防止死循环

与 DFS/Dijkstra 对比

算法	复杂度	本题缺陷
BFS	$O(N)$	无（完美适配）
DFS	$O(2^N)$	无法保证最短路径，易栈溢出
Dijkstra	$O(N^2)$	大材小用，代码更复杂

核心思路

初始化：
- 距离数组 dist[1..N] 初始化为 $-1$ （表示未访问）
- dist[A] = 0（起点距离为 0）
- 队列初始化：将 $A$ 入队

BFS 主循环：

while 队列非空:
    u = 出队
    if u == B: 提前终止（已找到最短路径）
    
    // 尝试向上移动
    v_up = u + K[u]
    if v_up 在 [1, N] 范围内 且 未访问:
        dist[v_up] = dist[u] + 1
        v_up 入队
        if v_up == B: 立即返回 dist[v_up]
    
    // 尝试向下移动
    v_down = u - K[u]
    if v_down 在 [1, N] 范围内 且 未访问:
        dist[v_down] = dist[u] + 1
        v_down 入队
        if v_down == B: 立即返回 dist[v_down]

终止条件：
- 队列空：检查 dist[B]，若仍为 $-1$ 则输出 $-1$
- 提前终止：BFS 过程中一旦到达 $B$ 立即输出结果（最优性保证）

边界情况处理

情况	处理方式	示例输入
$A = B$	直接输出 0	`5 3 3` + 任意 $K_i$
起点被阻塞 ( $K_A=0$ )	无法移动，输出 $-1$	`3 1 3` + `0 1 1`
$K_i=0$ 但非起点	跳过该节点（不影响其他路径）	`4 1 4` + `2 0 1 1`
单层楼 ( $N=1$ )	无论 $K_1$ 值， $A$ 必等于 $B$ ，输出 0	`1 1 1` + `100`

C++ 代码实现

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // 输入：总层数 N，起点 A，终点 B
    int N, A, B;
    cin >> N >> A >> B;
    
    // 输入每层的 K 值 (1-indexed，下标 1 到 N)
    vector<int> K(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> K[i];
    }

    // 边界情况 1：起点等于终点
    if (A == B) {
        cout << 0 << endl;
        return 0;
    }

    // dist[i] = 从 A 到 i 的最少按键次数，-1 表示未访问
    vector<int> dist(N + 1, -1);
    queue<int> q; // BFS 队列

    // BFS 初始化：起点入队
    dist[A] = 0;
    q.push(A);

    // BFS 主循环
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // 尝试向上移动：u -> u + K[u]
        int v_up = u + K[u];
        // 检查是否在有效范围内 [1, N] 且未访问
        if (v_up <= N && dist[v_up] == -1) {
            dist[v_up] = dist[u] + 1; // 更新距离
            // 提前终止：如果到达目标楼层 B
            if (v_up == B) {
                cout << dist[v_up] << endl;
                return 0;
            }
            q.push(v_up); // 新节点入队
        }

        // 尝试向下移动：u -> u - K[u]
        int v_down = u - K[u];
        // 检查是否在有效范围内 [1, N] 且未访问
        if (v_down >= 1 && dist[v_down] == -1) {
            dist[v_down] = dist[u] + 1; // 更新距离
            // 提前终止：如果到达目标楼层 B
            if (v_down == B) {
                cout << dist[v_down] << endl;
                return 0;
            }
            q.push(v_down); // 新节点入队
        }
    }

    // BFS 结束仍未到达 B
    cout << dist[B] << endl; // dist[B] 为 -1 时自动输出 -1
    return 0;
}

代码关键点解析

1-based 索引：
- 使用 vector<int> K(N + 1) 和 dist(N + 1)，下标 1~N 对应楼层
- 完美匹配输入格式（ $K_i$ 从第 1 层开始）
提前终止优化：
- 在更新 v_up/v_down 后立即检查是否等于 $B$
- 避免不必要的 BFS 扩展，提升性能（尤其在 $B$ 靠近 $A$ 时）
防死循环机制：
- 通过 dist[v] == -1 检查确保每个节点只访问一次
- 无需额外 visited 数组，dist 数组兼具距离记录和访问标记功能
边界处理：
- 起点=终点：开头直接判断，避免 BFS 开销
- 无效移动：通过 v_up <= N 和 v_down >= 1 严格检查范围

复杂度分析

时间复杂度： $O(N)$
- 每个节点最多入队 1 次，出队 1 次
- 每次处理 $O(1)$ 操作（两次移动尝试）
空间复杂度： $O(N)$
- dist 数组： $O(N)$
- 队列最坏情况存储 $O(N)$ 个节点

测试用例验证

题目示例：
```
5 1 5
3 3 1 2 5
```
执行过程：
- 起点 1：dist[1]=0
- 1 → 4 (1+3)，dist[4]=1
- 1 → -2 (无效)
- 4 → 6 (无效)
- 4 → 2 (4-2)，dist[2]=2
- 2 → 5 (2+3)，dist[5]=3 → 输出 3
无法到达：
```
2 1 2
0 1
```
执行过程：
- 起点 1：dist[1]=0
- 1 → 1+0=1 (已访问)
- 1 → 1-0=1 (已访问)
- 队列空，dist[2]=-1 → 输出 -1
起点=终点：
```
10 3 3
1 2 3 4 5 6 7 8 9 10
```
执行：直接输出 0

常见错误与避坑指南

忘记检查移动范围：
- 错误：直接访问 v_up = u + K[u] 而不检查 v_up <= N
- 后果：数组越界（Segmentation Fault）
未处理起点=终点：
- 错误：未在开头检查 A == B
- 后果：BFS 队列为空时错误输出 -1
死循环问题：
- 错误：未标记已访问节点（如用 DFS 未剪枝）
- 后果：1 → 2 → 1 → 2... 无限循环