leetcode1306

 1 class Solution:
 2     def bfs(self,arr,n,start,visited,path):
 3         while len(path) > 0:
 4             temp = []
 5             while len(path) > 0:
 6                 idx = path.pop()
 7                 for i in range(n):
 8                     if visited[i] == 1 or i == idx:
 9                         continue
10                     else:
11                         if i < idx and arr[i] == idx - i:
12                             if i == start:
13                                 return True
14                             visited[i] = 1
15                             temp.append(i)
16                         elif i > idx and arr[i] == i - idx:
17                             if i == start:
18                                 return True
19                             visited[i] = 1
20                             temp.append(i)
21             path = temp[:]
22         return False
23 
24 
25     def canReach(self, arr: 'List[int]', start: int) -> bool:
26         if arr[start] == 0:
27             return True
28         path = []#记录0的下标
29         n = len(arr)
30         visited = [0] * n
31         for i in range(n):
32             if arr[i] == 0:
33                 path.append(i)
34         return self.bfs(arr,n,start,visited,path)

算法思路：BFS。

先记录所有的0值元素的下标，作为初始集合。使用两层遍历，找出每到每个可达点存入下一层的集合。

使用visited进行缓存，过滤重复访问过的点，防止出现环，而死循环。