Untitled
unknown
c_cpp
2 years ago
2.0 kB
5
Indexable
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; } };
Editor is loading...