原题传送门—>leetcode

题目描述：

有一只跳蚤的家在数轴上的位置 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。
我的代码思路：

• blocks记录forbiden数组内容，blocks = 1则无法访问。
• blocks也充当visited数组的功能，当某点已经访问过一次了，blocks的值也置为1
• 队列保存着上次跳跃可能的位置，正数代表向右跳，负数代表向左跳。比如-20代表的是上次跳跃是向左跳到了位置为20的地方

不过我遇到很有意思的事情：（一下是AC版本1，请特别注意代码中的入队顺序）

class Solution {
public:
    int *blocks;
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        if(!x) return 0;
        blocks = new int[6005];
        memset(blocks,0,24020);
        for(vector<int>::iterator i = forbidden.begin(); i!= forbidden.end(); ++i){
            blocks[*i] = 1;
        }//路障标记
        return bfs(a,b,x);
    }
    int bfs(int a,int b, int x){
        queue<int> Q;
        Q.push(0);
        int step = 1;
        while(!Q.empty()){
            int size_tmp = Q.size();
            for(int i = 0; i < size_tmp; ++i){
                int tmp = Q.front();
                int isPosi = 1;//
                if(tmp <= 0) {
                    isPosi = 0;
                    tmp = -tmp;
                }
                int aa = tmp + a;
                int bb = tmp - b;
                if((aa == x)||((bb == x)&&(isPosi)))
                {
                    return step;
                }
                if((bb > 0)&&(!blocks[bb])&&(isPosi)) { //#左入队
                    Q.push(-bb);
                    blocks[bb] = 1;
                }
                if((aa <= 6000)&&(!blocks[aa])) {  //#右入队
                    Q.push(aa);
                    blocks[aa] = 1;
                }

                Q.pop();
            }
            ++step;
        }
        return -1;
    }
};

奇怪之处在于：假如将两个入队顺序调换过来就会Wa掉，没道理啊。

我又仔细比较了调换顺序的执行过程，发现了问题：

假如在step = 6时，存在两个点:
p点可以向右跳a步到达M点
q点可以向左跳b步到达M点

那么此时入队的应该是正数还是负数？

其实应该是正数，但是前面的写法无法应对这种情况。

改进版本：

class Solution {
public:
    int* blocks;
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        if (!x) return 0;
        blocks = new int[6005];
        memset(blocks, 0, 24020);
        for (vector<int>::iterator i = forbidden.begin(); i != forbidden.end(); ++i) {
            blocks[*i] = 1;
        }//路障标记
        return bfs(a, b, x);
    }
    int bfs(int a, int b, int x) {
        queue<int> Q;
        Q.push(0);
        int step = 1;
        while (!Q.empty()) {
            int size_tmp = Q.size();
            for (int i = 0; i < size_tmp; ++i) {
                int tmp = Q.front();
                int isPosi = 1;//
                if (tmp <= 0) {
                    isPosi = 0;
                    tmp = -tmp;
                }

                int aa = tmp + a;
                int bb = tmp - b;
                if ((aa == x) || ((bb == x) && (isPosi)))
                {
                    return step;
                }
                if ((aa <= 6000) && (blocks[aa] <= 0)) {

                    Q.push(aa);
                    blocks[aa] = 1;
                }
                if ((bb > 0) && (!blocks[bb]) && (isPosi)) {
                    Q.push(-bb);
                    blocks[bb] = -1;
                }


                Q.pop();
            }
            ++step;
        }
        return -1;
    }
};

至于第一版为什么恰巧能AC，我猜是数据不够强蒙混过关。。。