[Java] DP beats 100%
\npublic int minimumMoves(int[][] grid) {\n\tint n = grid.length;\n\tint[][][] dp = new int[n+1][n+1][2];\n\t//[i,j,0]=> horizontal\n\t//[i,j,1]=> vertical\n\tf
```\npublic int minimumMoves(int[][] grid) {\n\tint n = grid.length;\n\tint[][][] dp = new int[n+1][n+1][2];\n\t//[i,j,0]=> horizontal\n\t//[i,j,1]=> vertical\n\tfor(int i = 0; i <= n; i++){\n\t\tfor(int j = 0; j <= n; j++){\n\t\t\tdp[i][j][0] = Integer.MAX_VALUE/2;\n\t\t\tdp[i][j][1] = Integer.MAX_VALUE/2;\n\t\t}\n\t}\n\t//to make the initial position dp[1][1][0] as 0;\n\tdp[0][1][0] = -1;\n\tdp[1][0][0] = -1;\n\n\tfor(int i = 1; i <= n; i++){\n\t\tfor(int j = 1; j <= n; j++){\n\t\t\tboolean possibleFromRotate = false;\n\t\t\tboolean possibleFromAntiRotate = false;\n\t\t\t//could be from left\n\t\t\tif(grid[i-1][j-1] == 0 && j < n && grid[i-1][j] == 0){\n\t\t\t\tdp[i][j][0] = Math.min(dp[i][j-1][0], dp[i-1][j][0]) + 1;\n\t\t\t\tpossibleFromAntiRotate = true;\n\t\t\t}\n\n\t\t\tif(grid[i-1][j-1] == 0 && i < n && grid[i][j-1] == 0){\n\t\t\t\tdp[i][j][1] = Math.min(dp[i-1][j][1], dp[i][j-1][1]) + 1;\n\t\t\t\tpossibleFromRotate = true;\n\t\t\t}\n\t\t\t//could be from anti-rotate\n\t\t\tif(possibleFromAntiRotate && i<n && grid[i][j] == 0){\n\t\t\t\tdp[i][j][0] = Math.min(dp[i][j][0], dp[i][j][1]+1);\n\t\t\t}\n\t\t\t//could be from rotate\n\t\t\tif(possibleFromRotate && j<n && grid[i][j] == 0){\n\t\t\t\tdp[i][j][1] = Math.min(dp[i][j][1], dp[i][j][0]+1);\n\t\t\t}\n\n\t\t}\n\t}\n\n\treturn (dp[n][n-1][0] >= (Integer.MAX_VALUE/2)) ? -1 : dp[n][n-1][0];       \n}\n```
['Dynamic Programming']