Nhảy trò chơi III trong C++

Cho mảng arr các số nguyên không âm, bắt đầu tại chỉ số start. Tại chỉ số i, có thể nhảy đến i + arr[i] hoặc i - arr[i]. Kiểm tra xem có thể đến chỉ số nào có giá trị 0 hay không. Không được nhảy ra khỏi mảng.

Ví dụ: arr = [4,2,3,0,3,1,2], start = 5. Kết quả: true. Đường đi: 5 → 4 → 1 → 3 hoặc 5 → 6 → 4 → 1 → 3.

Giải thuật (BFS)

1. n = kích thước arr.
2. Khởi tạo hàng đợi q, thêm start. Tập visited chứa start.
3. Khi q không rỗng:
4. Lấy curr từ đầu hàng đợi.
5. Nếu arr[curr] == 0, trả về true.
6. Nếu curr + arr[curr] < n và chưa thăm, thêm vào q và visited.
7. Nếu curr - arr[curr] >= 0 và chưa thăm, thêm vào q và visited.
8. Trả về false nếu hết hàng đợi.

Ví dụ C++

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

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size();
        queue<int> q;
        q.push(start);
        set<int> visited;
        visited.insert(start);
        while(!q.empty()) {
            int curr = q.front(); q.pop();
            if(arr[curr] == 0) return true;
            if(curr + arr[curr] < n && !visited.count(curr + arr[curr])) {
                q.push(curr + arr[curr]);
                visited.insert(curr + arr[curr]);
            }
            if(curr - arr[curr] >= 0 && !visited.count(curr - arr[curr])) {
                q.push(curr - arr[curr]);
                visited.insert(curr - arr[curr]);
            }
        }
        return false;
    }
};

int main() {
    vector<int> v = {4,2,3,0,3,1,2};
    Solution ob;
    cout << (ob.canReach(v, 5));
    return 0;
}

Đầu vào

[4,2,3,0,3,1,2] 5

Đầu ra

1