Code & Func

第61天。

用广度优先遍历出来即可，为了防止死循环，所以我们需要一个visited数组来记录某个位置的元素是否已经访问过来（即是否压入了队列中）：

1
bool canReach(vector<int>& arr, int start) {
2
  queue<int> q;
3
  vector<int> visited(arr.size(), false);
4
  q.push(start);
5
  visited[start] = true;
6
  while(!q.empty()) {
7
    for(int i = 0, size = q.size(); i < size; i++) {
8
      start = q.front(); q.pop();
9
      if (arr[start] == 0) return true;
10
      if (start - arr[start] >= 0 && visited[start - arr[start]] == false) {
11
        q.push(start - arr[start]);
12
        visited[start - arr[start]] = true;
13
      }
14
      if (start + arr[start] < arr.size() && visited[start + arr[start]] == false) {
15
        q.push(start + arr[start]);
6 collapsed lines
16
        visited[start + arr[start]] = true;
17
      }
18
    }
19
  }
20
  return false;
21
}