1. 题目描述

1306 跳跃游戏III

2. 解题思路

1. 使用dfs或bfs的思想来进行遍历;
2. 使用used数组来表示当前位置是否被访问过。

3. 代码实现(DFS)

class Solution {
public:bool canReach(vector<int>& arr, int start) {int n = arr.size();vector<bool> used(n, false);function<bool(int)> dfs = [&](int idx) {if (idx < 0 || idx >= n))return false;if(used[idx])return false;if (arr[idx] == 0)return true;used[idx] = true;return dfs(idx - arr[idx]) || dfs(idx + arr[idx]);};return dfs(start);}
};

4. 代码实现(BFS)

class Solution {
public:bool canReach(vector<int>& arr, int start) {int n = arr.size();vector<bool> used(n, false);queue<int> que;que.push(start);while (!que.empty()) {auto it = que.front();que.pop();// 下标超出范围if (it < 0 || it >= n)continue;// 当前位置下标已访问过if (used[it])continue;if (arr[it] == 0)return true;used[it] = true;que.push(it + arr[it]);que.push(it - arr[it]);}return false;}
};