Minimum Moves to Reach Target with Rotations LeetCode solution in C++

1
class Solution {
2
 public:
3
  int n;
4
  set<vector<int>> visited;
5
  bool candown(vector<vector<int>> &grid, int x, int y, bool hor) {
6
    if (!hor) {
7
      if (x + 2 < n && grid[x + 1][y] == 0 && grid[x + 2][y] == 0 &&
8
          !visited.count({x + 1, y, hor})) {
9
        return true;
10
      }
11
    } else {
12
      if (x + 1 < n && y + 1 < n && grid[x + 1][y] == 0 && grid[x + 1][y + 1] == 0 &&
13
          !visited.count({x + 1, y, hor})) {
14
        return true;
15
      }
16
    }
17

18
    return false;
19
  }
20

21
  bool canright(vector<vector<int>> &grid, int x, int y, bool hor) {
22
    if (hor) {
23
      if (y + 2 < n && grid[x][y + 1] == 0 && grid[x][y + 2] == 0 &&
24
          !visited.count({x, y + 1, hor})) {
25
        return true;
26
      }
27
    } else {
28
      if (y + 1 < n && x + 1 < n && grid[x][y + 1] == 0 && grid[x + 1][y + 1] == 0 &&
29
          !visited.count({x, y + 1, hor})) {
30
        return true;
31
      }
32
    }
33

34
    return false;
35
  }
36

37
  bool canrot(vector<vector<int>> &grid, int x, int y, bool hor) {
38
    if (hor) {
39
      if (y + 1 < n && x + 1 < n && grid[x + 1][y] == 0 && grid[x + 1][y + 1] == 0 &&
40
          !visited.count({x, y, !hor})) {
41
        return true;
42
      }
43
    } else {
44
      if (x + 1 < n && y + 1 < n && grid[x][y + 1] == 0 && grid[x + 1][y + 1] == 0 &&
45
          !visited.count({x, y, !hor})) {
46
        return true;
47
      }
48
    }
49
    return false;
50
  }
51

52
  int minimumMoves(vector<vector<int>> &grid) {
53
    queue<array<int, 3>> q;
54
    q.push({0, 0, true});
55
    int ans = 0;
56
    n = grid.size();
57
    while (!q.empty()) {
58
      int size = q.size();
59
      while (size--) {
60
        auto a = q.front();
61
        q.pop();
62
        if (visited.count({a[0], a[1], a[2]})) {
63
          continue;
64
        }
65
        visited.insert({a[0], a[1], a[2]});
66
        int x = a[0];
67
        int y = a[1];
68
        if (x == n - 1 && y == n - 2 && a[2] == 1) {
69
          return ans;
70
        }
71
        if (candown(grid, x, y, a[2])) {
72
          q.push({x + 1, y, a[2]});
73
        }
74
        if (canrot(grid, x, y, a[2])) {
75
          q.push({x, y, !a[2]});
76
        }
77
        if (canright(grid, x, y, a[2])) {
78
          q.push({x, y + 1, a[2]});
79
        }
80
      }
81
      ans++;
82
    }
83
    return -1;
84
  }
85
};