aboutsummaryrefslogtreecommitdiff
path: root/jump_game3.cpp
blob: 03f7d3761b0de9f01b81333b1acf5c89ecae5576 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include "leetcode.h"

class Solution {
public:
  bool canReach(vector<int> &arr, int start) {
    vector<bool> visited(arr.size(), false);
    return dfs(arr, start, visited);
  }

private:
  bool dfs(vector<int> &arr, int curr, vector<bool> &k) {
    if ((curr < 0) || (curr >= arr.size()) || k[curr])
      return false;
    if (arr[curr] == 0)
      return true;
    k[curr] = true;
    return dfs(arr, curr + arr[curr], k) || dfs(arr, curr - arr[curr], k);
  }
};

int main() {
  Solution obj;
  vector<int> arr1 = {4, 2, 3, 0, 3, 1, 2}, arr2 = {3, 0, 2, 1, 2};
  testBool(obj.canReach(arr1, 5)); // true
  testBool(obj.canReach(arr1, 0)); // true
  testBool(obj.canReach(arr2, 2)); // false
}