Breadth first search || o(n*m) || Faster than 50% || clean Java code
Complexity\n- Time complexity: O(nm)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(nm)\n Add your space complexity here, e.g. O(n) \n\n# 
# Complexity\n- Time complexity: $$O(n*m)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n*m)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass State {\n    int x;\n    int y;\n    int other_x;\n    int other_y;\n    boolean isHorizontal;\n\n    public State(int x, int y, boolean isHorizontal) {\n        this.x = x;\n        this.y = y;\n        this.isHorizontal = isHorizontal;\n        int[] otherCell = getOtherCell();\n        other_x = otherCell[0];\n        other_y = otherCell[1];\n    }\n\n    public int[] getOtherCell() {\n        if (isHorizontal) return new int[] {x, y + 1};\n        else return new int[] {x + 1, y};\n    }\n\n    public State rotate() {\n        return new State(x, y, !isHorizontal);\n    }\n}\n\nclass Solution {\n    private final List<Integer[]> directions = List.of(\n            new Integer[]{0, 1},\n            new Integer[]{1, 0}\n    );\n    private final Queue<State> queue = new ArrayDeque<>();\n    private boolean[][][] visited;\n\n    public int minimumMoves(int[][] grid) {\n        queue.add(new State(0, 0, true));\n        visited = new boolean[grid.length][grid[0].length][2];\n        int steps = 0;\n        while (!queue.isEmpty()) {\n            int size = queue.size();\n            for (int count = 0; count < size; count++) {\n                State curr = queue.remove();\n                if (isTarget(curr, grid)) return steps;\n                int i = curr.x, j = curr.y, k = curr.isHorizontal ? 0 : 1;\n                if (visited[i][j][k]) continue;\n                visited[i][j][k] = true;\n                for (Integer[] direction: directions) {\n                    State newState = new State(i + direction[0], j + direction[1], curr.isHorizontal);\n                    addCell(newState, grid);\n                }\n                State rotated = curr.rotate();\n                if (isValidPivot(rotated, grid))\n                    addCell(rotated, grid);\n            }\n            steps++;\n        }\n        return -1;\n    }\n\n    private boolean isTarget(State curr, int[][] grid) {\n        return curr.x == grid.length - 1 && curr.y == grid[0].length - 2 && curr.isHorizontal;\n    }\n\n    private void addCell(State state, int[][] grid) {\n        int k = state.isHorizontal ? 0 : 1;\n        if (isValidCell(state.x, state.y, grid) && isValidCell(state.other_x, state.other_y, grid) &&\n                !visited[state.x][state.y][k]) {\n            queue.add(state);\n        }\n    }\n\n    private boolean isValidCell(int x, int y, int[][] grid) {\n        return isValidCoordinates(x, y, grid) && grid[x][y] != 1;\n    }\n\n    private boolean isValidCoordinates(int i, int j, int[][] grid) {\n        return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;\n    }\n\n    private boolean isValidPivot(State state, int[][] grid) {\n        int x = state.x + 1, y = state.y + 1;\n        return isValidCoordinates(x, y, grid) && grid[x][y] != 1;\n    }\n}\n```
['Breadth-First Search', 'Java']