LeetCode 1345. 跳跃游戏 IV

798236606

传送门：https://leetcode-cn.com/problems/jump-game-iv/

BFS + 哈希表剪枝

class Solution {
public:
    int minJumps(vector<int>& arr) {
        //这一步for循环可以不加，可以规避掉大量连续相同值造成的时间浪费
        for (int i = 1; i < arr.size() - 1; ++i)
        {
            int j  = i + 1; 
            
            while (j < arr.size() && arr[j] == arr[i]) ++j;
            arr.erase(arr.begin() + i + 1, arr.begin() + j);
        }

        struct Node{
            int id, step;
        };        

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

        vector<bool> vis(n, false);
        queue<Node> q;
        
        q.push({0, 0});
        vis[0] = true;
        
        while (!q.empty())
        {
            Node now = q.front();
            q.pop();
            
            if (now.id == arr.size() - 1) return now.step;
            
            if (!vis[now.id + 1])
            {
                q.push({now.id + 1, now.step + 1});
                vis[now.id + 1] = true;
            }
            
            if (now.id > 0 && !vis[now.id - 1]) 
            {
                q.push({now.id - 1, now.step + 1});
                vis[now.id - 1] = true;
            }

            if (m.find(arr[now.id]) != m.end())
            {
                for (int i: m[arr[now.id]])
                {
                    if (!vis[i])
                    {
                        q.push({i, now.step + 1}); 
                        vis[i] = true;
                    }                    
                }

                m.erase(m.find(arr[now.id]));//找到一个相同值，则所有同值的位置都不可再通过同值的规则跳             
            }
        }
        
        return -1;//若未找到路径，返回-1
    }
};