Leetcode 1210: Minimum Moves to Reach Target with Rotations

https://leetcode.com/problems/minimum-moves-to-reach-target-with-rotations/description/

Notes:

This question looks like can be solved by dp, but actually the state transition equation is not easy to be converted into code. (since we cannot simply run the loop from smaller index to larger, or from larger to smaller, due to the possible rotations.)

This question is asking for the minimum distance, so it can be naturally solved by BFS.

There are two positions: one is horizontal and the other is vertical. So we need to distinguish them.

Another thing is that the final valid state must be horizontal.


See the code below:

class Solution {
public:
    int minimumMoves(vector<vector<int>>& grid) {
        int res = 0, n = grid.size();
        vector<vector<int>> visit(n*n, vector<int>(2, 0));
        queue<pair<int, int>> q;
        q.push({0*n+1, 0});
        visit[1][0] = 1;
        while(q.size()) {
            ++res;
            int k = q.size();
            for(int i=0; i<k; ++i) {
                auto t = q.front();
                q.pop();
                int x = t.first/n, y = t.first%n, z = t.second;
                if(z==0) {//if horizontal
                    if(y+1<n && grid[x][y+1] == 0 && !visit[x*n+y+1][0]) {
                        if(x == n-1 && y + 1 == n-1) return res;
                        q.push({x*n+y+1, 0});
                        visit[x*n+y+1][0] = 1;
                    }
                    if(x+1<n && y-1>=0 && grid[x+1][y-1]==0 && grid[x+1][y]==0) {
                        if(!visit[(x+1)*n+y-1][1]) {
                            q.push({(x+1)*n+y-1, 1});
                            visit[(x+1)*n+y-1][1] = 1;
                        }
                        if(!visit[(x+1)*n+y][0]) {
                            if(x+1 == n-1 && y == n-1) return res;
                            q.push({(x+1)*n + y, 0});
                            visit[(x+1)*n+y][0] = 1;
                        }
                    }
                }
                if(z==1) {//if vertical
                    if(x+1<n && grid[x+1][y] == 0 && !visit[(x+1)*n+y][1]) {
                        q.push({(x+1)*n+y, 1});
                        visit[(x+1)*n+y][1] = 1;
                    }
                    if(x-1>= 0 && y+1<n && grid[x-1][y+1]==0 && grid[x][y+1]==0) {
                        if(!visit[(x-1)*n+y+1][0]) {
                            q.push({(x-1)*n+y+1, 0});
                            visit[(x-1)*n+y+1][0] = 1;
                        }
                        if(!visit[(x)*n+y+1][1]) {
                            q.push({(x)*n + y+ 1, 1});
                            visit[(x)*n+y+1][1] = 1;
                        }
                    }
                }
            }
        }
        return -1;
    }
};