Leetcode.1654 到家的最少跳跃次数

题目链接

Leetcode.1654 到家的最少跳跃次数 Rating ： 2124

题目描述

有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发，到达它的家。

跳蚤跳跃的规则如下：

• 它可以 往前 跳恰好 a 个位置（即往右跳）。
• 它可以 往后 跳恰好 b 个位置（即往左跳）。
• 它不能 连续 往后跳 2 次。
• 它不能跳到任何 forbidden数组中的位置。

跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。

给你一个整数数组 forbidden，其中 forbidden[i]是跳蚤不能跳到的位置，同时给你整数 a， b 和 x ，请你返回跳蚤到家的最少跳跃次数。

如果没有恰好到达 x 的可行方案，请你返回 -1 。

示例 1：

输入：forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
输出：3
解释：往前跳 3 次（0 -> 3 -> 6 -> 9），跳蚤就到家了。

示例 2：

输入：forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
输出：-1

示例 3：

输入：forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
输出：2
解释：往前跳一次（0 -> 16），然后往回跳一次（16 -> 7），跳蚤就到家了。

提示：

• $1<=forbidden.length<=1000$
• $1<=a,b,forbidden[i]<=2000$
• $0<=x<=2000$
• forbidden中所有位置互不相同。
• 位置 x 不在 forbidden中。

解法：bfs

本题很明显是用 bfs 求解。

我们首先要求出 搜索的上界$n$。因为如果我们不规定上界的话，它就可以一直往前跳，这样的话时间复杂度是我们不能接受的。

我这里直接给出结论，搜索的上界 n = m a x { m a x { f o r b i d d e n [ i ] } + a + b , x + b } n = max\{ max\{ forbidden[i]\} + a + b , x + b\} n=max{max{forbidden[i]}+a+b,x+b}。主要是我自己不会证明。。。。

证明可以参考这篇题解：证明

确定了上界之后，我们就可以使用 bfs 求解最短路了。

我们定义 $dist[t][0]$ 是由 前跳 到位置 $t$ 的最短跳数，定义 $dist[t][1]$ 是由 后跳 到位置 $t$ 的最短跳数。

用 $banned$ 记录禁止到达的位置。

从起点 0 开始 bfs 即可。

时间复杂度： $O(n)$

C++代码：

using PII = pair<int,int>;

class Solution {
public:
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        int f = *max_element(forbidden.begin(),forbidden.end());
        //搜索的最大边界
        int n = max(f + a + b,x + b);

        //不能到达的点
        bool banned[n + 1];
        memset(banned,false,sizeof banned);
        for(auto x:forbidden) banned[x] = true;

        // 0 前跳 ， 1 后跳
        int dist[n + 1][2];
        memset(dist,0x3f,sizeof dist);
        dist[0][0] = 0;

        queue<PII> q;
        q.push({0,0});

        while(!q.empty()){
            auto [t,pre] = q.front();
            q.pop();
            if(t == x){
                return dist[t][pre];
            }

            //后跳，上一次是前跳 本次才能后跳
            if(pre == 0 && t - b >= 0 && !banned[t-b] && dist[t][pre] + 1 < dist[t-b][1]){
                dist[t-b][1] = dist[t][pre] + 1;
                q.push({t-b,1});
            }

            //前跳
            if(t + a <= n && !banned[t+a] && dist[t][pre] + 1 < dist[t+a][0]){
                dist[t+a][0] = dist[t][pre] + 1;
                q.push({t+a,0});
            }
        }
        return -1;
    }
};