Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
2.0 kB
2
Indexable
Never
class Solution {
public:
    struct Info {
        int coord;
        int weight;
        bool canJumpBack;
    };
    
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        std::unordered_set<int> forbidden_set = { forbidden.begin(), forbidden.end() };
        int max_forbidden = std::max(*std::max_element(forbidden.begin(), forbidden.end()), x);
        std::stack<Info> paths;
        if (forbidden_set.find(a) != forbidden_set.end()) return -1;
        if (0 == x) return 0;
        if (a == x) return 1;
        paths.push({ a, 1, true });
        int min = -1;
        std::unordered_set<int> visited = { 0, a };
        while (!paths.empty()) {
            Info path = paths.top();
            paths.pop();
            int jump_a = path.coord + a;
            int jump_b = path.coord - b;
            if (jump_b > max_forbidden + a) continue;
            int weight = path.weight + 1;
            if (min != -1 && weight > min) continue;
            if (path.canJumpBack) {
                if ((jump_b > 0) && (visited.find(jump_b) == visited.end()) && (forbidden_set.find(jump_b) == forbidden_set.end())) {
                    if (jump_b == x) {
                        if ((min == -1) || (min > weight)) {
                            min = weight;
                        }
                    }
                    else {
                        paths.push({ jump_b, weight, false });
                        visited.insert(jump_b);
                    }
                }
            }
            if (forbidden_set.find(jump_a) == forbidden_set.end()) {
                if (jump_a == x) {
                    if ((min == -1) || (min > weight)) {
                        min = weight;
                    }
                }
                else {
                    paths.push({ jump_a, weight, true });
                }
            }
        }
        return min;
    }
};