1345. 跳跃游戏 IV

题面:

1345. 跳跃游戏 IV

 

题解:bfs即可,不过要注意判重,相同值的加入一次即可。

代码:

class Solution {
public:
    int minJumps(vector<int>& arr) {
           map< int, vector<int> >ma;
           queue<pair<int, int> >q;
           int n = arr.size();
           for(int i = 0;i < n;i ++)
           {
               ma[arr[i]].emplace_back(i);
           }
           q.push({0, 0});
           map<int,int>mb;
           while(q.size())
           {
                auto t = q.front();
                q.pop();
                int step = t.first;
                int x = t.second;
                if(x == n-1)return step;
                if(ma.count(arr[x]))
                {
                    for(auto i : ma[arr[x]])
                    {
                        if(!mb.count(i))
                        {
                                mb[i] = 1;
                                q.push({step+1,i});
                        }
                    }
                    ma.erase(arr[x]);
                }
                if(x+1<n&&!mb.count(x+1))
                {
                    mb[x + 1] = 1;
                    q.push({step+1,x+1});
                }
                if(x-1>=0&&!mb.count(x-1))
                {
                    mb[x - 1] = 1;
                    q.push({step+1,x-1});
                }
           }
           return -1;
    }
};

 

上一篇:专转本图像与图形及应用-笔记


下一篇:猜数字小游戏