[C++] DP with Speed 99% Memory 91%
Top-down dynamic programming. dp[i][j] is a pair<int, int> where dp[i][j].first is the minimum moves from starting point to (i, j) with head in (i, j) and tail 
Top-down dynamic programming. `dp[i][j]` is a `pair<int, int>` where `dp[i][j].first` is the minimum moves from starting point to (i, j) with head in (i, j) and tail in (i, j-1) (horizontal), and `dp[i][j].second` is the minimum moves from starting point to (i, j) with head in (i, j) and tail in (i-1, j) (vertical). If it\'s impossible for the snake to be in that position, set the value to be `-1`. For either horizontal or vertical position, there\'re 3 ways for the snake to move from last position to new positon: move down, move right, rotate. Calculate the minimum move for each way and store the smallest one in `dp[i][j]`.\n\n```\nclass Solution {\npublic:\n    int minimumMoves(vector<vector<int>>& grid) {\n        int n = grid.size();\n        vector<vector<pair<int, int>>> dp(n, vector<pair<int,int>>(n));\n        int ho, ho1, ho2, ho3, ve, ve1, ve2, ve3;\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                if (i == 0 && j <= 1) dp[i][j] = {0, -1};\n                else if (grid[i][j] == 1) dp[i][j] = {-1, -1};\n                else if (i == 0) {\n                    if (dp[i][j-1].first==-1) dp[i][j] = {-1, -1};\n                    else dp[i][j] = {dp[i][j-1].first+1, -1};\n                }\n                else if (i == 1 && j == 0) {\n                    if (grid[1][1] == 1) dp[i][j] = {-1, -1};\n                    else dp[i][j] = {-1,1};\n                }\n                else if (j == 0) {\n                    if (dp[i-1][j].second==-1) dp[i][j] = {-1, -1};\n                    else dp[i][j] = {-1, dp[i-1][j].second+1};\n                }\n                else {\n                    ho1 = dp[i][j-1].first==-1?-1:dp[i][j-1].first+1;\n                    ho2 = (dp[i-1][j].first==-1||grid[i][j-1]==1)?-1:dp[i-1][j].first+1;\n                    if (i==n-1 || grid[i+1][j]==1 || grid[i+1][j-1]==1 || dp[i][j-1].second == -1) ho3 = -1;\n                    else ho3 = dp[i][j-1].second + 2;\n                    if (ho1 == -1 && ho2 == -1) ho = ho3;\n                    else if (ho1 == -1) ho = ho2;\n                    else if (ho2 == -1) ho = ho1;\n                    else ho = min(ho1, ho2);\n                    if (grid[i-1][j] == 1) ve = -1;\n                    else {\n                        ve1 = dp[i-1][j].second==-1?-1:dp[i-1][j].second+1;\n                        if (j == n-1 || grid[i][j+1]==1||dp[i-1][j+1].first==-1) ve2 = -1;\n                        else ve2 = dp[i-1][j+1].first+1;\n                        ve3 = dp[i][j-1].second== -1?-1:dp[i][j-1].second+1;\n                        if (ve1 == -1 && ve3 == -1) ve = ve2;\n                        else if (ve1 == -1) ve = ve3;\n                        else if (ve3 == -1) ve = ve1;\n                        else ve = min(ve1, ve3);\n                    }\n                    dp[i][j] = {ho, ve};\n                }\n            }\n        }\n        return dp[n-1][n-1].first;\n    }\n};\n```\n\n![image](https://assets.leetcode.com/users/images/5c882116-21d5-4323-861e-0f0ad9f2907c_1597283162.628977.png)\n\n
[]