package interview;

// 这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。
//请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
//注意，不管是什么情况下，你都无法跳到数组之外。
//链接：https://leetcode-cn.com/problems/jump-game-iii
public class CanReach {

    public static boolean canReach(int[] arr,int start) {
        int N = arr.length;
        boolean[] visited = new boolean[N];

        return brackTrace(arr,start,visited);
    }

    public static boolean brackTrace(int[] arr,int index,boolean[] visited){
        if (index < 0 || index >= arr.length || visited[index]){
            return false;
        }

        if (arr[index] == 0){
            return true;
        }

        visited[index] = true;
        return brackTrace(arr,index + arr[index],visited) || brackTrace(arr,index + arr[index],visited);
    }


}