发表于 2024.07.25

• 简单地通过BFS遍历即可，直到找到0后返回True。需要注意下边界条件，以及将遍历过的位置进行标记。

  class Solution:
      def canReach(self, arr: List[int], start: int) -> bool:
          queue = deque([start])
          visited = [False] * len(arr)
  
          while queue:
              index = queue.popleft()
              if arr[index] == 0:
                  return True
  
              for next_index in (index + arr[index], index - arr[index]):
                  if 0 <= next_index < len(arr) and not visited[next_index]:
                      visited[next_index] = True
                      queue.append(next_index)
  
          return False

  C++的做法：

  class Solution {
  public:
      bool canReach(vector<int>& arr, int start) {
          if (arr[start] == 0) return true;
          queue<int> Q;
          Q.push(start);
          vector<bool> visited(arr.size(), false);
          while (!Q.empty()) {
              auto index = Q.front();
              Q.pop();
              for (auto &next_index : {index + arr[index], index - arr[index]}) {
                  if (next_index >= 0 && next_index < arr.size() && !visited[next_index]) {
                      if (arr[next_index] == 0) return true;
                      visited[next_index] = true;
                      Q.push(next_index);
                  }             
              }
          }
          return false;
      }
  };

• LC 题目链接