# Untitled

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;
}```