1306. 跳躍游戲 III

這里有一個非負整數數組?arr，你最開始位于該數組的起始下標?start?處。當你位于下標?i?處時，你可以跳到?i + arr[i]?或者?i - arr[i]。

請你判斷自己是否能夠跳到對應元素值為 0 的?任一?下標處。

注意，不管是什么情況下，你都無法跳到數組之外。

示例 1：

輸入：arr = [4,2,3,0,3,1,2], start = 5
輸出：true
解釋：
到達值為 0 的下標 3 有以下可能方案： 
下標 5 -> 下標 4 -> 下標 1 -> 下標 3 
下標 5 -> 下標 6 -> 下標 4 -> 下標 1 -> 下標 3 

示例 2：

輸入：arr = [4,2,3,0,3,1,2], start = 0
輸出：true 
解釋：
到達值為 0 的下標 3 有以下可能方案： 
下標 0 -> 下標 4 -> 下標 1 -> 下標 3

示例 3：

輸入：arr = [3,0,2,1,2], start = 2
輸出：false
解釋：無法到達值為 0 的下標 1 處。 

提示：

• 1 <= arr.length <= 5 * 10^4
• 0 <= arr[i] <?arr.length
• 0 <= start < arr.length

class Solution {int flag = 0;public boolean canReach(int[] arr, int start) {boolean[] vis = new boolean[arr.length];dfs(arr,vis,start);//深搜return flag==1?true:false;}public void dfs(int[] arr,boolean[] vis,int start){if(flag==1)return;//如果訪問到0了，直接返回if(vis[start] == true)return;//如果訪問過了，則跳出if(start>=arr.length||start<0)return;//如果超出范圍了，則跳出vis[start] = true;//將該點設置為已訪問int right = start + arr[start];int left = start - arr[start];if(right<arr.length){//若沒超過界限dfs(arr,vis,right);//訪問右節點if(arr[right]==0)flag=1;//如果為0，則直接跳出}if(left>=0){//若沒超過界限dfs(arr,vis,left);//訪問左節點if(arr[left]==0)flag=1;}}
}