题目
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.
解题思路
从初始位置开始，进行BFS或者DFS，判断是否能到达0的位置
代码
class Solution:
def canReach(self, arr: List[int], start: int) -> bool:
n = len(arr)
s = {start}
q = [start]
while q:
cur = q.pop()
for nei in (cur + arr[cur], cur - arr[cur]):
if 0 <= nei < n:
if arr[nei] == 0:
return True
if nei not in s:
q.append(nei)
s.add(nei)
return False
