跳跃游戏 III (Jump Game III)

1. 题目描述

题目背景： 在图论和搜索算法中，判定路径的可达性是核心考点。本题将数组下标抽象为图的节点，将跳跃规则抽象为有向边，要求判断从起点出发是否能到达目标节点。

任务描述： 给定一个非负整数数组 arr 和一个起始下标 start。 当你位于下标 i 时，你可以跳跃到 i + arr[i] 或 i - arr[i]。 在任何时刻，你都必须保证跳跃后的下标在数组范围之内（即 $0 \le \text{下标} < \text{arr.length}$）。 请判断你是否能够跳跃到任意一个权值为 $0$ 的下标处。

输入格式：

1. 第一行包含两个整数 $n$ 和 $start$（$1 \le n \le 5 \times 10^4, 0 \le start < n$），分别表示数组长度和起始下标。
2. 第二行包含 $n$ 个整数，表示数组 $arr$ 的元素（$0 \le arr[i] < n$）。

输出格式： 如果能到达权值为 $0$ 的下标，输出 true，否则输出 false。

---

样例 1： 输入：

7 5
4 2 3 0 3 1 2

输出：

true

(解释：到达值为 0 的下标 3 有多种方式：下标 5 -> 4 -> 1 -> 3 或 下标 5 -> 6 -> 4 -> 1 -> 3)

样例 2： 输入：

7 0
4 2 3 0 3 1 2

输出：

true

(解释：下标 0 -> 4 -> 1 -> 3)

样例 3：

5 2
3 0 2 1 2

输出：

false

(解释：无法到达下标 1，因为该下标权值为 0)

数据范围：

• $1 \le n \le 5 \times 10^4$
• $0 \le arr[i] < n$

---

2. 预备知识点

1. 搜索算法 (BFS/DFS)：本题是典型的路径可达性问题。
2. 图的抽象：将数组索引看作节点 $0 \dots n-1$，边为 $i \to i+arr[i]$ 和 $i \to i-arr[i]$。
3. 状态标记 (Visited)：在搜索过程中必须记录已访问的下标，防止因循环跳跃导致的死循环。
4. 边界检查：每次跳跃前需判定新下标是否溢出数组边界。

---

3. 启发式思维引导

请拿出草稿纸，跟随教练的思路进行推理：

第一步：建模分析

画出样例 3 的逻辑图。下标 2 的权值是 2，你可以跳到 $2+2=4$ 或 $2-2=0$。

• 思考：这像不像在走迷宫？每个下标就是一间房，房里的数字告诉你可以往左/右走多远。
• 动作：在纸上标出每个下标之间的指向关系。

第二步：确定搜索策略

• BFS (广度优先)：像水波纹一样扩散。从 start 开始，先把一步能到的下标入队，再处理两步能到的。
• DFS (深度优先)：像钻洞一样。从 start 选一个方向跳到底，跳不动了再回溯。
• 关键点：无论哪种，你都需要一个布尔数组 vis[n]。一旦跳到一个已经去过的下标，就不要再处理它了。

第三步：时间和空间复杂度思考

• 时间：每个下标最多入队/访问一次。总共有 $n$ 个下标，每个下标最多尝试两个跳跃方向。复杂度为 $O(n)$。
• 空间：需要 vis 数组存储状态，BFS 需要队列，DFS 需要递归栈。空间复杂度为 $O(n)$。

第四步：时间复杂度优化建议

• 在搜索过程中，一旦发现 arr[i] == 0，立刻返回 true 并结束程序。
• 对于 $n=5 \times 10^4$，递归深度可能达到 $5 \times 10^4$，在 NOI 环境下需注意栈空间限制（建议使用 BFS 或扩大系统栈）。

---

4. 算法流程图 (基于 BFS 逻辑)

graph TD
    A(开始) --> B(初始化布尔数组 vis 为全 false)
    B --> C(创建队列 Q 并将 start 入队)
    C --> D(标记 vis{start} 为 true)
    
    D --> E{Q 是否为空}
    E -- 是 --> F(输出 false 并结束)
    E -- 否 --> G(弹出队首下标 u)
    
    G --> H{arr{u} 是否等于 0}
    H -- 是 --> I(输出 true 并结束)
    
    H -- 否 --> J(计算下一位置 next1 = u + arr{u})
    J --> K{next1 是否在范围内 且 未访问}
    K -- 是 --> L(将 next1 入队并标记访问)
    K -- 否 --> M(计算下一位置 next2 = u - arr{u})
    
    L --> M
    M --> N{next2 是否在范围内 且 未访问}
    N -- 是 --> O(将 next2 入队并标记访问)
    N -- 否 --> E
    O --> E

---

5. 读题关键词总结

在 NOI 竞赛中，读到以下词汇时要迅速联想对应模型：

1. “能否到达” / “判定路径”：
   • 直觉指示：搜索类问题（BFS/DFS）或并查集。
2. “下标 i 跳跃到 i + arr[i]”：
   • 直觉指示：显式图论模型。每个节点出度固定为 2。
3. “非负整数”：
   • 警示：如果 $arr[i]$ 为 0，表示原地踏步，搜索时需注意处理，但本题目标就是找 0，所以遇到 0 即可停止。
4. “范围之内”：
   • 动作：代码中必须有 if (pos >= 0 && pos < n) 的判断。

教练点评： 这道题属于搜索入门题。在 NOI 中，这通常作为大题的一个子模块或者普及组的签到题出现。最核心的得分点在于：严谨的边界控制和不重复访问节点的标记处理。加油！