Java concise DFS with explanation - 8 ms (beats 99% runtime and 100% memory)
The idea is to use two memoization and visited tables - one each for horizontal and vertical position of the snake.\n\n```\n\tpublic int minimumMoves(int[][] gr
The idea is to use two memoization and visited tables - one each for horizontal and vertical position of the snake.\n\n```\n\tpublic int minimumMoves(int[][] grid) {\n        if(grid == null) return -1;\n        int n = grid.length;\n        int result = minimumMoves(0, 0, 0, 1, grid, new int[n][n][2], new boolean[n][n][2]);\n        return (result == Integer.MAX_VALUE) ? -1 : result;\n    }\n    \n    private int minimumMoves(int x1, int y1, int x2, int y2, int[][] grid, int[][][] memo, boolean[][][] visited){\n        int n = grid.length;\n\t\t/*return error if this position is invalid*/\n        if(x1 >= n || x2 >= n || y1 >= n || y2 >= n || grid[x1][y1] == 1 || grid[x2][y2] == 1) return Integer.MAX_VALUE;\n        if(x1 == n-1 && y1 == n-2 && x2 == n-1 && y2 == n-1) return 0; //return 0 if we reached target\n        \n        int index = (x1 == x2) ? 0 : 1; //determine the index of memo or visited table to look into\n        if(memo[x1][y1][index] != 0) return memo[x1][y1][index]; //if memo already contains valid value, return it\n        if(visited[x1][y1][index]) return Integer.MAX_VALUE; //else it is already visited, we did not find any valid path from this position\n        \n        visited[x1][y1][index] = true;        \n        int result = Integer.MAX_VALUE;\n        \n\t\t/*Determine the number of minimum moves from this position depending on whether it is vertical or horizontal*/\n\t\t//horizontal\n        if(x1 == x2){\n            result = Math.min(result, minimumMoves(x2, y2, x2, y2+1, grid, memo, visited)); //right\n            result = Math.min(result, minimumMoves(x1+1, y1, x2+1, y2, grid, memo, visited)); //down\n            if(x1+1 < n && y1+1 < n && grid[x1+1][y1+1] == 0){\n                result = Math.min(result, minimumMoves(x1, y1, x1+1, y1, grid, memo, visited)); //rotation\n            }\n        }\n\t\t//vertical\n        else{\n            result = Math.min(result, minimumMoves(x2, y2, x2+1, y2, grid, memo, visited)); //down\n            result = Math.min(result, minimumMoves(x1, y1+1, x2, y2+1, grid, memo, visited)); //right\n            if(x1+1 < n && y1+1 < n && grid[x1+1][y1+1] == 0){\n                result = Math.min(result, minimumMoves(x1, y1, x1, y1+1, grid, memo, visited)); //rotation\n            }\n        }\n        \n        if(result < Integer.MAX_VALUE) result++; //increment the result as we need to consider a move from current position\n        memo[x1][y1][index] = result; //store the result in the appropriate memo table\n        return result;\n    }
[]