Minimum Jumps to Reach Home LeetCode solution in C++

1
class Solution {
2
 public:
3
  typedef pair<int, bool> pi;
4
  int minimumJumps(vector<int> &forbidden, int a, int b, int x) {
5
    set<int> st(forbidden.begin(), forbidden.end());
6
    vector<vector<int>> vis(2, vector<int>(10000, 0));
7
    vis[0][0] = 1;
8
    vis[1][0] = 1;
9
    queue<pi> q;
10
    q.push({0, true});
11
    int ans = 0;
12
    while (!q.empty()) {
13
      int n = q.size();
14
      for (int i = 0; i < n; i++) {
15
        int curr = q.front().first;
16
        bool canJumpBackward = q.front().second;
17
        q.pop();
18
        if (curr == x) return ans;
19
        int p1 = curr + a;
20
        int p2 = curr - b;
21
        if (p1 < 10000 && vis[0][p1] == 0 && st.find(p1) == st.end()) {
22
          q.push({p1, true});
23
          vis[0][p1] = 1;
24
        }
25
        if (p2 >= 0 && vis[1][p2] == 0 && st.find(p2) == st.end() && canJumpBackward == true) {
26
          q.push({p2, false});
27
          vis[1][p2] = 1;
28
        }
29
      }
30
      ans++;
31
    }
32
    return -1;
33
  }
34
};