LeetCode 1210. Minimum Moves to Reach Target with Rotations

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    static constexpr int DIRS[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; // downward, rightward, rotate
public:
    int minimumMoves(vector<vector<int>>& grid) {
        int n = grid.size();
        bool st[n][n][2];
        memset(st, 0, sizeof(st));
        st[0][0][0] = 1;
        vector<tuple<int, int, int>> q;
        q.emplace_back(0, 0, 0);
        for (int step = 1; !q.empty(); ++step) {
            vector<tuple<int, int, int>> nxt;
            for (const auto &[X, Y, S] : q) {
                for (const auto &d : DIRS) {
                    int x = X + d[0], y = Y + d[1], s = S ^ d[2]; // tail
                    int x2 = x + s, y2 = y + (s ^ 1); // head
                    if (x2 < n && y2 < n && !st[x][y][s] && grid[x][y] == 0 && grid[x2][y2] == 0
                        && (d[2] == 0 || grid[x + 1][y + 1] == 0)) {
                            if (x == n - 1 && y == n - 2) return step;
                            st[x][y][s] = 1;
                            nxt.emplace_back(x, y, s);
                        }
                }
            }
            q = move(nxt);
        }
        return -1;
    }
};