【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++