# 【LeetCode】 1306. Jump Game III

## Description
> Given an array of non-negative integers `arr`, you are initially positioned at `start` index of the array. When you are at index `i`, you can jump to `i + arr[i]` or `i - arr[i]`, check if you can reach to any index with value 0.
> Notice that you can not jump outside of the array at any time.

> 給予一個非負整數的陣列 `arr`，你最開始在陣列中索引值為 `start` 的位置。當你在索引值 `i` 時，你可以跳到 `i + arr[i]` 或是 `i - arr[i]`，檢查你是否可以到達任何值為 0 的索引值。
> 注意你任何時候都不該跳出陣列之外。

## Example:

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: 
All possible ways to reach at index 3 with value 0 are: 
index 5 -> index 4 -> index 1 -> index 3 
index 5 -> index 6 -> index 4 -> index 1 -> index 3 

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true 
Explanation: 
One possible way to reach at index 3 with value 0 is: 
index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

## Solution

* 一維版本的走迷宮，或是想成圖論中確認兩個 node 之間是否有路徑
* 起點是 `start`
* 終點是值為 `0` 的所有點
* 因為不需要求出最短路徑，只需要確定是否可以到達，可以直接用 DFS 求解
* 為了加速，用了一個陣列去存哪些點我已經走過了
* 下面範例 code 使用遞迴解，每個 node 有兩條路可以走(往前或往後)，其中一條到達就可以，因此用 OR 連接

### Code

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

###### tags: `LeetCode` `C++`