Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
3.1 kB
1
Indexable
Never
#include <vector>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
#include <queue>
#include <algorithm>

class Solution {
public:
    struct Info {
        int coord;
        int weight;
        bool canJumpBack;
    };

    int minimumJumps(std::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 (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 (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 });
                }
            }
            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);
                    }
                }
            }
        }
        return min;
    }
};

int main() {
    std::vector<int> vec = { 1401,832,1344,173,1529,1905,1732,277,1490,650,1577,1886,185,1728,1827,1924,1723,1034,1839,1722,1673,1198,1667,538,911,1221,1201,1313,251,752,40,1378,1515,1789,1580,1422,907,1536,294,1677,1807,1419,1893,654,1176,812,1094,1942,876,777,1850,1382,760,347,112,1510,1278,1607,1491,429,1902,1891,647,1560,1569,196,539,836,290,1348,479,90,1922,111,1411,1286,1362,36,293,1349,667,430,96,1038,793,1339,792,1512,822,269,1535,1052,233,1835,1603,577,936,1684,1402,1739,865,1664,295,977,1265,535,1803,713,1298,1537,135,1370,748,448,254,1798,66,1915,439,883,1606,796 };
    int a = 19;
    int b = 18;
    int x = 1540;
    Solution sol;
    std::cout << sol.minimumJumps(vec, a, b, x) << std::endl;
    /*int counter = 0;
    int val = 0;
    for (int i = 0; i < 1000; ++i) {
        val += a;
        ++counter;
        if (val == x) break;
        if (val > b) {
            val -= b;
            ++counter;
        }
    }
    std::cout << counter << std::endl;
    */
    return 0;
}