1654. 到家的最少跳跃次数(bfs，多维信息)

zk6696 / 2023-08-30 / 原文

1654. 到家的最少跳跃次数

本题目是经典bfs，我们在进行广搜的时候，不仅要记录某个点是否走过，当前位置和步数，还要记录上一次是否是向后走，来决定此时是否能向后走。

由于广搜有最短的性质，所以某个点只能入队一次。

以往在记录多维信息时候，常用pair嵌套与结构体，有点不方便；从本题题解中学到了c ++ 中的tuple类型，可以用来记录多维信息。

技巧：在面对二维轴上移动时候可以将点位置与方向相乘来进行哈希。

class Solution {
public:
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        unordered_set<int> st, pos;
        for(auto &it: forbidden) {
            st.insert(it);
        }

        int mx = max(*max_element(forbidden.begin(), forbidden.end()) + a, x) + b;

        auto f = [&]() {
            queue<tuple<int, int, int>> q;
            q.push({0, 0, 1});

            while(q.size()) {
                auto [t0, t1, t2] = q.front();
                q.pop();
                if(t0 == x) return t1;
                //往前走
                if(!st.count(t0 + a) && !pos.count(t0 + a) && t0 + a <= mx) {
                    q.push({t0 + a, t1 + 1, 1});
                    pos.insert(t0 + a);
                }

                //往后走
                if(t0 - b < 0 || t2 == -1) continue;
                if(!st.count(t0 - b) && !pos.count(-(t0 - b)) && t0 - b <= mx) {
                    q.push({t0 - b, t1 + 1, -1});
                    pos.insert(-(t0 - b));
                }
            }

            return -1;
        };

        return f();
    }
};

若维度继续增加，方法二就不适用了，可以进行拆分，将每个维度都用哈希表存起来。

class Solution {
public:
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        unordered_set<int> st, pos1, pos2;
        for(auto &it: forbidden) {
            st.insert(it);
        }

        int mx = max(*max_element(forbidden.begin(), forbidden.end()) + a, x) + b;

        auto f = [&]() {
            queue<tuple<int, int, int>> q;
            q.push({0, 0, 1});

            while(q.size()) {
                auto [t0, t1, t2] = q.front();
                q.pop();
                if(t0 == x) return t1;
                //往前走
                if(!st.count(t0 + a) && !pos1.count(t0 + a) && t0 + a <= mx) {
                    q.push({t0 + a, t1 + 1, 1});
                    pos1.insert(t0 + a);
                }

                //往后走
                if(t0 - b < 0 || t2 == -1) continue;
                if(!st.count(t0 - b) && !pos2.count(t0 - b) && t0 - b <= mx) {
                    q.push({t0 - b, t1 + 1, -1});
                    pos2.insert(t0 - b);
                }
            }

            return -1;
        };

        return f();
    }
};