Задача: 1345. Jump Game IV
Сложность: hard

Дан массив целых чисел arr, изначально вы находитесь на первом индексе массива.

За один шаг вы можете прыгнуть с индекса i на индекс:

- i + 1, где: i + 1 < arr.length.
- i - 1, где: i - 1 >= 0.
- j, где: arr[i] == arr[j] и i != j.

Вернуть минимальное количество шагов, чтобы достичь последнего индекса массива.

Обратите внимание, что нельзя прыгать за пределы массива в любой момент времени.

Пример:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

👨‍💻 Алгоритм:

1⃣Построить граф, где ключи - значения из массива, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов.

2⃣Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя.

3⃣Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь.

😎 Решение:

class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        if (n <= 1) return 0;

        unordered_map<int, vector<int>> graph;
        for (int i = 0; i < n; i++) {
            graph[arr[i]].push_back(i);
        }

        vector<int> curs = {0};
        unordered_set<int> visited = {0};
        int step = 0;

        while (!curs.empty()) {
            vector<int> nex;

            for (int node : curs) {
                if (node == n - 1) return step;

                for (int child : graph[arr[node]]) {
                    if (visited.find(child) == visited.end()) {
                        visited.insert(child);
                        nex.push_back(child);
                    }
                }

                graph[arr[node]].clear();

                if (node + 1 < n && visited.find(node + 1) == visited.end()) {
                    visited.insert(node + 1);
                    nex.push_back(node + 1);
                }
                if (node - 1 >= 0 && visited.find(node - 1) == visited.end()) {
                    visited.insert(node - 1);
                    nex.push_back(node - 1);
                }
            }

            curs = nex;
            step++;
        }

        return -1;
    }
};

Ставь 👍 и забирай 📚 Базу знаний