# 1306. Jump Game III
###### tags: `Leetcode` `Medium` `DFS` `BFS`
Link: https://leetcode.com/problems/jump-game-iii/
## 思路
注意如果可能会跳出去就不会往那个方向跳
之所以不用记录每个node的结果(也就是从start有没有可能跳到value为0的地方) 是因为对于一条path只要有一个是true 那么其他分支全都不用看 最上面的直接返回true 所以如果碰到visited过的node说明他一定是走不动target node
但如果recursion里面不是只有一个true就返回true的话就需要记录结果
## Code

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        visited = [False]*len(arr)
        def dfs(curr):
            if visited[curr]: return False
            visited[curr] = True
            if arr[curr] == 0: return True
            if curr-arr[curr]>=0 and dfs(curr-arr[curr]): return True
            return curr+arr[curr]<len(arr) and dfs(curr+arr[curr])
        return dfs(start)

class Solution {
    public boolean canReach(int[] arr, int start) {
        boolean[] visited = new boolean[arr.length];
        return dfs(arr, visited, start);
    }
    private boolean dfs(int[] arr, boolean[] visited, int start){
        if(visited[start]) return false;
        visited[start] = true;
        if(arr[start]==0){
            return true;
        }
        if(start-arr[start]>=0 && dfs(arr, visited, start-arr[start])) return true;
        return start+arr[start]<=arr.length-1 && dfs(arr, visited, start+arr[start]);
    }
}