Simple in place DP solution trades speed for memory, beats 97% still
IntuitionThis is a simple in place DP approach, the dp vector contains the shortest path to a cell in the currently active row, with the orientation and column
# Intuition
This is a simple in place DP approach, the dp vector contains the shortest path to a cell in the currently active row, with the orientation and column determined by the indices. 

We pass over this array multiple times, each time we treat the old value as the value corresponding to the shortest path to the previous row. This reduces memory usage from $O(n^2)$ to $O(n)$. The downside is that we are forced to consider all possible states whereas BFS only considers states along a minimal path. In the case of a completely empty grid, both approaches will take $O(n^2)$ time. Conversely on a completely blocked grid, the BFS algorithm will terminate early while the DP algorithm will still visit every state.  

We use a large number to indicate that a path is impossible. Usually you want to use something like `INT_MAX` but our dp will attempt to increment the value so we need something smaller. $4n$ is a reasonable upper bound on the maximum possible moves to solve the problem. You should be able to prove that rotating after every move cannot possibly be optimal and improve it further but it won't make the code any better. 
 
# Complexity
- Time complexity:
$O(n^2)$

- Space complexity:
$O(n)$

# Code
```cpp []
constexpr int impossible = 100000; 
class Solution {
public:
    int minimumMoves(vector<vector<int>>& grid) {
        const size_t n = grid.size();
        // use a large number to specify that this movement is impossible
        // 0 is horizontal, 1 is vertical
        vector<vector<int>> dp(2, vector(n + 1, impossible));  
        // our starting point
        dp[0][1] = -1; 
        for(size_t i = 0; i < n; i++) {
            for(size_t j =0; j < n; j++) {
                int dp1 = dp[1][j + 1];
                // handle horizontal
                if(grid[i][j] == 1 || j + 1 == n || grid[i][j + 1] == 1) {
                    dp[0][j + 1] = impossible;
                } else {
                    dp[0][j + 1] = min(dp[0][j + 1] + 1, dp[0][j] + 1);
                    // check rotation from this position
                    if(i + 1 < n && grid[i + 1][j] == 0 && grid[i + 1][j + 1] == 0) {
                        dp1 = min(dp[0][j + 1], dp1);
                    }
                }
                // handle vertical
                if(grid[i][j] == 1 || i + 1 == n || grid[i + 1][j] == 1) {
                    dp[1][j + 1] = impossible;
                } else {
                    dp[1][j + 1] = min(dp[1][j] + 1, 1 + dp1);
                    // check rotation from this position
                    if(j + 1 < n && grid[i][j + 1] == 0 && grid[i + 1][j + 1] == 0) {
                        dp[0][j + 1] = min(dp[0][j + 1], 1 + dp[1][j + 1]);  
                    }
                }
            }
        }
        if(dp[0][n-1] >= impossible) {
            return -1;
        }
        return dp[0][n-1];
    }
};
```
['Dynamic Programming', 'C++']