leetcode/1306.cpp at main · Centinoughty/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Jump game III
// MEDIUM

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size();

        queue<int> q;
        vector<bool> visited(n, false);

        q.push(start);
        visited[start] = false;

        while (!q.empty()) {
            int top = q.front(); q.pop();

            if (arr[top] == 0) return true;

            int l = top - arr[top];
            int r = top + arr[top];

            if (l >= 0 && !visited[l]) {
                visited[l] = true;
                q.push(l);
            }

            if (r < n && !visited[r]) {
                visited[r] = true;
                q.push(r);
            }
        }

        return false;
    }
};