1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>

const int INF = 0x3fff'ffff;

class Solution {
public:
    int minJumps(std::vector<int>& arr) {
        int n = arr.size();
        std::unordered_map<int, std::vector<int>> edges;
        for (int i = 0; i < n; ++i) {
            edges[arr[i]].push_back(i);
        }
        
        std::vector<int> dist(n, INF);
        std::queue<int> q;
        dist[0] = 0;
        q.push(0);
        while (!q.empty()) {
            int u = q.front();
            int d = dist[u];
            q.pop();
            if (u > 0 && dist[u] + 1 < dist[u - 1]) {
                dist[u - 1] = dist[u] + 1;
                q.push(u - 1);
            }
            if (u < n - 1 && dist[u] + 1 < dist[u + 1]) {
                dist[u + 1] = dist[u] + 1;
                q.push(u + 1);
            }
            auto it = edges.find(arr[u]);
            if (it == edges.end()) {
                continue;
            }
            const vector<int>& next_indices = it->second;
            for (auto& v : next_indices) {
                if (INF == dist[v]) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
            edges.erase(it);
        }
        return dist.back();
    }
};