เกมกระโดด III ใน C++

สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มไม่ติดลบ arr เราอยู่ที่ดัชนีเริ่มต้น start เมื่ออยู่ที่ดัชนี i เราสามารถกระโดดไปที่ i + arr[i] หรือ i - arr[i] ตรวจสอบว่าเราสามารถถึงดัชนีใดดัชนีหนึ่งที่มีค่า 0 ได้หรือไม่ ต้องระวังไม่ให้กระโดดออกนอกอาร์เรย์

ตัวอย่าง: arr = [4,2,3,0,3,1,2], เริ่มจาก 5 ผลลัพธ์คือ true เพราะเคลื่อนที่ได้ 5 → 4 → 1 → 3 หรือ 5 → 6 → 4 → 1 → 3

ขั้นตอนการแก้ปัญหา (BFS)

• n := ขนาดของ arr
• กำหนดคิว q ใส่ start เข้าไป, กำหนดเซต visited ใส่ start เข้าไป
while คิวไม่ว่าง:
• curr := ตัวหน้าของ q, ลบตัวหน้าออกจาก q
• ถ้า arr[curr] == 0 คืนค่า true
• ถ้า curr + arr[curr] < n และยังไม่ได้ไปเยี่ยม curr + arr[curr] แล้ว:
  • ใส่ curr + arr[curr] เข้า q และ visited
• ถ้า curr - arr[curr] >= 0 และยังไม่ได้ไปเยี่ยม curr - arr[curr] แล้ว:
  • ใส่ curr - arr[curr] เข้า q และ visited
• คืนค่า false

ตัวอย่างโค้ด (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));
}

อินพุต

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

เอาต์พุต

1