[Java] dp + memorization search[11ms]
horizontal direction: dp[x][y][0] means the min move times when the snake tail is at (x, y) and its direction is horizontal.\n * vertical direction: dp[x][y][1]
* horizontal direction: dp[x][y][0] means the min move times when the snake tail is at (x, y) and its direction is horizontal.\n * vertical direction: dp[x][y][1] means the min move times when the snake tail is at (x, y) and its direction is vertical.\n\n**state transfer:**\n\n1.  for horizontal direction, the snake can move right, move down or rotate clock-wise\n\n\t* \t right:               precondition -> grid[x][y+2]=0\n\t*   down:                precondition -> grid[x+1][y]=0 & grid[x+1][y+1]=0\n\t*  rotate clock-wise:   precondition -> grid[x+1][y]=0 & grid[x+1][y+1]=0\n\t\n\t**if all satisfy these three conditions\n    dp[x][y][0] = Math.min(dp[x+1][y][0], dp[x+1][y][0], dp[x][y][1]) + 1**\n\n2. for vertical direction, the snake can move right, move down or rotate counterclockwise\n\n\t *  down: precondition -> grid[x+2][y]=0\n\t *  right: precondition -> grid[x][y+1]=0 & grid[x+1][y+1]=0\n\t * rotate counterclockwise -> grid[x][y+1]=0 & grid[x+1][y+1]=0\n\t \n\t**if all satisfy these three conditions\n\tdp[x][y][1] = Math.min(dp[x+1][y][1], dp[x][y+1][1], dp[x][y][0])+1**\n\n**attention**: to prevent same position go repeated rotate clockwise or counterclockwise, need set visited symbol.\n\n```\nprivate int search(int[][] grid, int x, int y, boolean isH, Integer[][][] mem, boolean[][][] vis) {\n\t\t// invalid state\n        if (x < 0 || y < 0 || x >= m || y >= n) return Integer.MAX_VALUE;\n        if (isH && y >= n-1) return Integer.MAX_VALUE;\n        if (!isH && x >= m-1) return Integer.MAX_VALUE;\n        // reach the aim ending point.\n        if (isH && x==m-1 && y==n-2) return 0;\n\t\t// caculated\n        if (mem[x][y][isH ? 0 : 1] != null) {\n            return mem[x][y][isH ? 0 : 1];\n        }\n\t\t// has been visited, this means this state is caculating\n        if (vis[x][y][isH ? 0: 1]) return Integer.MAX_VALUE;\n        // set visit symbol\n        vis[x][y][isH ? 0: 1] = true;\n        int ans = Integer.MAX_VALUE;\n        // horizontal\n        if (isH) {\n            // right\n            if (y+2 < n && grid[x][y+2]==0) {\n                ans = Math.min(ans, search(grid, x, y+1, isH, mem, vis));\n            }\n            // down and rotate clock-wise\n            if (x+1 < m && grid[x+1][y]==0 && grid[x+1][y+1]==0) {\n                int way1 = search(grid, x+1, y, isH, mem, vis);   // down\n                int way2 = search(grid, x, y, !isH, mem, vis); // rotate clockwise\n                ans = Math.min(ans, Math.min(way1, way2));\n            }\n        } else {\n            // down\n            if (x+2 < m && grid[x+2][y] == 0) {\n                ans = Math.min(ans, search(grid, x+1, y, isH, mem, vis));\n            }\n            // right or rotate counterclockwise\n            if (y+1 < n && grid[x][y+1]==0 && grid[x+1][y+1]==0) {\n                int way1 = search(grid, x, y+1, isH, mem, vis); // right\n                int way2 = search(grid, x, y, !isH, mem, vis); // rotate counterclockwise\n                ans = Math.min(ans, Math.min(way1, way2));\n            }\n        }\n\t\t// ans= Integer.MAX_VALUE means no solution to move to aim ending.\n        if (ans < Integer.MAX_VALUE) {\n            ans += 1;\n        }\n        mem[x][y][isH ? 0:1] = ans;\n        return ans;\n    }\n    public int minimumMoves(int[][] grid) {\n        if ((m=grid.length)<=1 || (n=grid[0].length)<=1) return -1;\n        Integer[][][] mem = new Integer[m][n][2];\n        boolean[][][] vis = new boolean[m][n][2];\n        if (grid[0][0]==1 || grid[0][1] == 1) {\n            return -1;\n        }\n        int ans = search(grid, 0, 0, true, mem, vis);\n        return ans==Integer.MAX_VALUE ? -1: ans;\n\n    }\n```
['Dynamic Programming', 'Memoization']