aboutsummaryrefslogtreecommitdiff
path: root/other/min_jump_reach_home.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/min_jump_reach_home.cpp')
-rw-r--r--other/min_jump_reach_home.cpp44
1 files changed, 0 insertions, 44 deletions
diff --git a/other/min_jump_reach_home.cpp b/other/min_jump_reach_home.cpp
deleted file mode 100644
index 7510c8c..0000000
--- a/other/min_jump_reach_home.cpp
+++ /dev/null
@@ -1,44 +0,0 @@
-#include "leetcode.h"
-
-class Solution {
-public:
- int minimumJumps(vector<int> &forbidden, int a, int b, int x) {
- unordered_set<int> f(forbidden.begin(), forbidden.end());
- vvd visited(2, vector<int>(5000));
- queue<pair<int, bool>> qp;
- qp.push({0, false});
- visited[0][0] = 1;
- visited[1][0] = 1;
- int ans = 0;
- while (!qp.empty()) {
- int len = qp.size();
- while (len > 0) {
- len--;
- int curr = qp.front().first;
- bool flag = qp.front().second;
- if (curr == x)
- return ans;
- qp.pop();
- int forward = curr + a, backward = curr - b;
- if (forward < 5000 && visited[0][forward] == 0 && !f.count(forward)) {
- qp.push({forward, false});
- visited[0][forward] = 1;
- }
- if (backward >= 0 && visited[1][backward] == 0 && !f.count(backward) &&
- !flag) {
- qp.push({backward, true});
- visited[1][backward] = 1;
- }
- }
- ans++;
- }
- return ans;
- }
-};
-
-int main() {
- Solution obj;
- vector<int> forbidden = {14, 4, 18, 1, 15};
- int a = 3, b = 15, x = 9;
- cout << obj.minimumJumps(forbidden, a, b, x);
-}