Jump Game IV ใน C++

คำอธิบายโจทย์

มีอาร์เรย์ arr เริ่มที่ index 0 กระโดดได้ 3 แบบ: i+x, i-x (ในขอบเขต), หรือ j ที่ arr[i]==arr[j] และ i!=j หาจำนวนขั้นตอนน้อยที่สุดไปถึง index สุดท้าย

ตัวอย่าง

arr = [20,-5,-5,25,20,5,5,5,1,25] → Output: 3

เส้นทาง: 0 → 4 → 3 → 9 (กระโดดค่าเท่ากัน 20, แล้ว 25, แล้ว 25)

วิธีแก้ปัญหา

ใช้ BFS (Breadth-First Search):

สร้าง map: ค่า → รายการ index ที่มีค่านั้น
เริ่มจาก index 0, ระดับ 0
แต่ละขั้นตอนลองกระโดด: i-1, i+1, และทุก index ที่มีค่าเท่ากัน
Mark visited ป้องกันซ้ำ
สำคัญ: หลังใช้ค่า arr[curr] แล้ว ให้ลบออกจาก map เพื่อไม่วนซ้ำ
เจอ index สุดท้าย → คืนระดับปัจจุบัน

การทำงานของโค้ด

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

class Solution {
public:
    int minJumps(vector<int>& arr) {
        map<int, vector<int>> m;
        int n = arr.size();
        for(int i=0; i= 0 && !visited.count(i-1)) {
                    q.push(i-1); visited.insert(i-1);
                }
                if(i+1 < n && !visited.count(i+1)) {
                    q.push(i+1); visited.insert(i+1);
                }
                for(int idx : m[arr[curr]]) {
                    if(!visited.count(idx)) {
                        q.push(idx); visited.insert(idx);
                    }
                }
                if(m.count(arr[curr])) m.erase(arr[curr]); // สำคัญ!
            }
        }
        return -1;
    }
};

int main() {
    Solution ob;
    vector<int> v = {20,-5,-5,25,20,5,5,5,1,25};
    cout << ob.minJumps(v);
    return 0;
}

อินพุต