JAVE intuitive BFS solution
Two BFS. \n1st BFS to push box as regular BFS. \n2nd BFS to check if the person can reach the box inside 1st BFS\n\nBFS to push box. For each positon of box, ch
Two BFS. \n1st BFS to push box as regular BFS. \n*2nd BFS to check if the person can reach the box inside 1st BFS\n\nBFS to push box. For each positon of box, check if player can push it.\nBox can be pushed only when it has two opposite adajacent grids are empty\n\t1. traverse the grid to find the location of player, box, target, and set their grid value to \'.\'\n\t2. Use 4d boolean array visited (boolean[box_x][box_y][player_x][player_y]) to record visited box\n\t3. In the BFS Queue, it is an array of box_x, box_y, player_x, player_y, step\n\t4. During BFS, check the 2 adajcent grids for the box in x and y direction. \nIf both they are within grid and have \'.\', do second BFS to see if the player can reach the position \n\nTime complexity: O(n^2*m^2)\nSpace complexity: O(n*m)\nn, m is the grid width and length\n\n```\nclass Solution {\n    public int minPushBox(char[][] grid) {\n        int m = grid.length;\n        int n = grid[0].length;\n        int[] box = {-1, -1};\n        int[] player = {-1, -1};\n        int[] target = {-1, -1};\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid[i][j] == \'S\') {\n                    player = new int[]{i, j};\n                } else if (grid[i][j] == \'B\') {\n                    box = new int[]{i, j};\n                } else if (grid[i][j] == \'T\') {\n                    target = new int[]{i, j};\n                }\n            }\n        }\n        grid[player[0]][player[1]] = \'.\';\n        grid[box[0]][box[1]] = \'.\';\n        grid[target[0]][target[1]] = \'.\';\n        boolean[][][][] visited = new boolean[m][n][m][n];\n        Queue<int[]> queue = new ArrayDeque<>();\n        queue.offer(new int[]{box[0], box[1], player[0], player[1], 0});\n        visited[box[0]][box[1]][player[0]][player[1]] = true;\n        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n        while(!queue.isEmpty()) {\n            int[] cur = queue.poll();\n            for (int i = 0; i < 4; i += 2) {\n                int x1 = cur[0] + dirs[i][0];\n                int y1 = cur[1] + dirs[i][1];\n                int x2 = cur[0] + dirs[i + 1][0];\n                int y2 = cur[1] + dirs[i + 1][1];\n                if (inGrid(m, n, x1, y1, grid) && inGrid(m, n, x2, y2, grid)) {\n                    if (!visited[x1][y1][x2][y2] && canReach(grid, cur[2], cur[3], x2, y2, new int[]{cur[0], cur[1]})) {\n                        if (x1 == target[0] && y1 == target[1]) {\n                            return cur[4] + 1;\n                        }\n                        visited[x1][y1][x2][y2] = true;\n                        queue.offer(new int[]{x1, y1, x2, y2, cur[4] + 1});\n                    }\n                    if (!visited[x2][y2][x1][y1] && canReach(grid, cur[2], cur[3], x1, y1, new int[]{cur[0], cur[1]})) {\n                        if (x2 == target[0] && y2 == target[1]) {\n                            return cur[4] + 1;\n                        }\n                        visited[x2][y2][x1][y1] = true;\n                        queue.offer(new int[]{x2, y2, x1, y1, cur[4] + 1});\n                    }\n                }\n\n            }\n        }\n        return -1;\n    }\n    private boolean canReach(char[][]grid, int px, int py, int tx, int ty, int[] box) {\n        int m = grid.length;\n        int n = grid[0].length;\n        Queue<int[]> queue = new ArrayDeque<>();\n        boolean[][] visited = new boolean[grid.length][grid[0].length];\n        queue.offer(new int[]{px, py});\n        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n        while(!queue.isEmpty()) {\n            int[] cur = queue.poll();\n            if (cur[0] == tx && cur[1] == ty) {\n                return true;\n            }\n            for (int[] dir : dirs) {\n                int x = cur[0] + dir[0];\n                int y = cur[1] + dir[1];\n                if (inGrid(m, n, x, y, grid) && !visited[x][y]) {\n                    if (x == tx && y == ty) {\n                        return true;\n                    }\n                    if (x == box[0] && y == box[1]) {\n                        continue;\n                    }\n                    queue.offer(new int[]{x, y});\n                    visited[x][y] = true;\n                }\n            }\n        }\n        return false;\n    }\n\n\n    private boolean inGrid(int m, int n, int x, int y, char[][]grid) {\n        return x >= 0 && y >= 0 && x < m && y < n && grid[x][y] != \'#\'; // can be target\n    }\n}\n```
[]