跳跃游戏IV

从0位置跳到末位置，每次可以往左跳、往右跳一格，或跳到有与该位置相同数值的地方，求最小跳跃次数

1. 广度优先搜索+哈希预处理+动态规划

class Solution {
public:
    vector<int> dp;//dp[i]表示到达i位置最小操作数
    int minJumps(vector<int>& arr) {
        int n =arr.size();
        map<int,vector<int>> m;
        for(int i=0;i<n;i++)
            m[arr[i]].push_back(i);//存储对应值的坐标

        dp.resize(n,INT_MAX);
        queue<int> q;
        q.push(0);
        int depth = 0;
        while(!q.empty()){
            if(dp[n-1]!=INT_MAX) return dp[n-1];//剪枝
            int k = q.size();
            for(int i=0;i<k;i++){
                int cur = q.front();
                q.pop();
                if(cur<0||cur>=n) continue;//跳过越界
                if(dp[cur]<=depth) continue;//跳过重复
                dp[cur] = depth;
                //接下来把能加入的坐标加入
                q.push(cur+1);
                q.push(cur-1);
                if(!m.count(arr[cur])) continue;//没有相同值，表示已经被扫描过了
                for(int j=0;j<m[arr[cur]].size();j++)
                    q.push(m[arr[cur]][j]);
                 m.erase(arr[cur]);
            }
            depth++;//下一层操作数加一
        }
        return dp[n-1];
    }
};