跳跃游戏III

BFS
跳跃游戏III

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

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        if (arr[start] == 0) return true;
        int n = arr.size();
        vector<bool> st(n);//这里写bool st[n]不行，似乎是因为生成了随机值，应当进行初始化
        queue<int> q;
        q.push(start);
        st[start] = true;
        while (!q.empty())
        {
            int t = q.front();
            q.pop();

            if (t + arr[t] < n && !st[t + arr[t]])
            {
                if (arr[t + arr[t]] == 0) return true;
                q.push(t + arr[t]);
                st[t + arr[t]] = true;
            }
            if (t - arr[t] >= 0 && !st[t - arr[t]])
            {
                if (arr[t - arr[t]] == 0) return true;
                q.push(t - arr[t]);
                st[t - arr[t]] = true;
            } 
        }
        return false;
    }
};