第61天。
今天的题目是Jump Game III:
用广度优先遍历出来即可，为了防止死循环，所以我们需要一个visited数组来记录某个位置的元素是否已经访问过来（即是否压入了队列中）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| bool canReach(vector<int>& arr, int start) {
queue<int> q;
vector<int> visited(arr.size(), false);
q.push(start);
visited[start] = true;
while(!q.empty()) {
for(int i = 0, size = q.size(); i < size; i++) {
start = q.front(); q.pop();
if (arr[start] == 0) return true;
if (start - arr[start] >= 0 && visited[start - arr[start]] == false) {
q.push(start - arr[start]);
visited[start - arr[start]] = true;
}
if (start + arr[start] < arr.size() && visited[start + arr[start]] == false) {
q.push(start + arr[start]);
visited[start + arr[start]] = true;
}
}
}
return false;
}
|