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

Cho mảng số nguyên arr. Bắt đầu tại chỉ số 0. Mỗi bước có thể nhảy từ i đến: i+x (i+x

Ví dụ với arr = [20,-5,-5,25,20,5,5,5,1,25], đầu ra là 3. Cần 3 nhảy: 0 → 4 → 3 → 9.

Giải pháp

Sử dụng BFS để tìm đường đi ngắn nhất:

• Xây dựng map m: giá trị → danh sách chỉ số
• Queue BFS từ chỉ số 0, tập visited
• Mỗi level: xử lý tất cả nút trong queue hiện tại
  • Nếu đến cuối mảng: trả về level
  • Thử nhảy i-1, i+1 (nếu hợp lệ và chưa thăm)
  • Thử nhảy đến tất cả chỉ số cùng giá trị arr[curr] (nếu chưa thăm)
  • Sau khi xử lý giá trị arr[curr], xóa khỏi map để tránh lặp lại
• Trả về -1 nếu không tìm thấy

Ví dụ mã C++

#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 < n; i++) 
            m[arr[i]].push_back(i); 
        
        set<int> visited; 
        visited.insert(0); 
        queue<int> q; 
        q.push(0); 
        
        for (int lvl = 0; !q.empty(); lvl++) { 
            int sz = q.size(); 
            while (sz--) { 
                int curr = q.front(); 
                q.pop(); 
                
                if (curr == n - 1) return lvl; 
                
                int i = curr; 
                if (i - 1 >= 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 j = 0; j < m[arr[curr]].size(); j++) { 
                    if (!visited.count(m[arr[curr]][j])) { 
                        q.push(m[arr[curr]][j]); 
                        visited.insert(m[arr[curr]][j]); 
                    } 
                } 
                
                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; 
}

Đầu vào

{20,-5,-5,25,20,5,5,5,1,25}

Đầu ra

3