Java | Dynamic Programing 13 ms faster than 95%
Here I use a 3-dimension dp table to solve the problem, \nI regard the position of snake as "HEAD" and "DIRECTION" (0 as left-right and 1 as up-down)\nFor the s
Here I use a 3-dimension dp table to solve the problem, \nI regard the position of snake as "HEAD" and "DIRECTION" (0 as left-right and 1 as up-down)\nFor the status of snake (i,j,k),\nThe status transforming formular can be written below:\ndp[i][j][k] = Math.min(dp[i-1][j][k],dp[i][k-1][k],dp[i][j][k^1])------left,up,and rotate\nThe base cases can be a little complicated.\n\n```\nClass Solution {\n    public int minimumMoves(int[][] grid) {\n        int n = grid.length;\n        int[][][] dp = new int[n][n][2];\n        \n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++){\n                for(int k=0;k<2;k++){\n                    if(i==0&&j==0&&k==0)\n                        dp[i][j][k]=0;\n                    else if(grid[i][j]==1)\n                        dp[i][j][k]=Integer.MAX_VALUE;\n                    else if(k==0&&(j+1>=n||grid[i][j+1]==1))\n                        dp[i][j][k]=Integer.MAX_VALUE;\n                    else if(k==1&&(i+1>=n||grid[i+1][j]==1))\n                        dp[i][j][k]=Integer.MAX_VALUE;\n                    else{\n                        int choice1 = i-1>=0? dp[i-1][j][k]:Integer.MAX_VALUE;//go down\n                        int choice2 = j-1>=0? dp[i][j-1][k]:Integer.MAX_VALUE;//go right\n                        int tempMinChoice = Math.min(choice1,choice2);\n                        dp[i][j][k] = tempMinChoice==Integer.MAX_VALUE? tempMinChoice:(tempMinChoice+1);\n                    }\n                }\n                //rotate\n                if(i+1<n&&j+1<n&&grid[i][j+1]!=1&&grid[i+1][j+1]!=1&&dp[i][j][1]!=Integer.MAX_VALUE&&dp[i][j][0]>dp[i][j][1]+1) \n                    dp[i][j][0]=dp[i][j][1]+1;\n                if(i+1<n&&j+1<n&&grid[i+1][j]!=1&&grid[i+1][j+1]!=1&&dp[i][j][0]!=Integer.MAX_VALUE&&dp[i][j][1]>dp[i][j][0]+1) \n                    dp[i][j][1]=dp[i][j][0]+1;\n            }\n        }\n        return dp[n-1][n-2][0]==Integer.MAX_VALUE? -1:dp[n-1][n-2][0];\n    }\n}\n```\nVote if it helps you :) Thx
['Dynamic Programming', 'Java']