[Java] BFS (17ms), Explained with comments
Two things need to pay attention:\n While trying to recorded to visited position of Box, we need to include an additional dimension to record which direction th
Two things need to pay attention:\n* While trying to recorded to **visited position of Box**, we need to include an additional dimension to record which direction the Player pushed the box from. For example, there are 4 previous positions that the Box can arrive position (x, y). We have to treat those 4 states separately.\n* While checking if the Player is able to reach the correct position to make a valid push, we need to **set the Box position as an obstacle(#)** since the Player cannot walk pass Box. Also, we need to keep track of **the previous position of the Player** after making the push.\n\nI have included comments in my code. Hope this helps.\n\n```\nclass Solution {\n    private char[][] G;\n    private int rows;\n    private int cols;\n    private int[] dir = new int[]{-1,0,1,0,-1};\n    public int minPushBox(char[][] grid) {\n        // Sanity check\n        if(grid == null || grid.length == 0 || grid[0].length == 0)     \n            return-1;\n        \n        rows = grid.length;\n        cols = grid[0].length;\n        G = grid;\n        \n        // Find the location of the Target, the Box and the Player.\n        int[] tLoc = new int[2];\n        int[] pLoc = new int[2];\n        int[] bLoc = new int[2];\n        for(int r = 0; r < rows; r++) {\n            for(int c = 0; c < cols; c++) {\n                if(G[r][c] == \'S\')\n                    pLoc = new int[]{r,c};\n                \n                if(G[r][c] == \'T\') \n                    tLoc = new int[]{r,c};\n                \n                if(G[r][c] == \'B\')  \n                    bLoc = new int[]{r,c};\n                \n                // Set those location to be Floor so we can BFS easier\n                if(G[r][c] != \'#\')  \n                    G[r][c] = \'.\';\n            }\n        }\n        \n        // BFS on Box\n        return bfs(pLoc, bLoc, tLoc);\n    }\n    \n    // BFS for Box\n    private int bfs(int[] p, int[] b, int[] t) {\n        Queue<int[]> queue = new LinkedList<>();\n        // Keep a record of the Player position along with the Box positon\n        int[] L = new int[]{b[0],b[1],p[0],p[1]};\n        \n        // An extra dimension to keep track of where the Box is pushed from\n        boolean[][][] visited = new boolean[rows][cols][4];\n        queue.offer(L);\n        int step = 0;\n        \n        // Standard BFS\n        while(!queue.isEmpty()) {\n            int len = queue.size();\n            while(len > 0) {\n                int[] loc = queue.poll();\n                // Mark the current Box position as an obstacle\n                G[loc[0]][loc[1]] = \'#\';\n                \n                // Use directional array to check 4 directions\n                for(int i = 0; i < 4; i++) {\n                    int deltaR = dir[i];\n                    int deltaC = dir[i+1];\n                    int newR = loc[0] + deltaR;\n                    int newC = loc[1] + deltaC;\n                    \n                    // If the new Box position is in bound \n                    // && the Play can reach that position\n                    // && that position is a Floor\n                    // && that position is visited with the current push direction "i"\n                    if(inBound(newR,newC) \n                            && reachable(loc[2],loc[3],loc[0]-deltaR,loc[1]-deltaC)\n                            && G[newR][newC] != \'#\' \n                            && !visited[newR][newC][i]) {\n                        \n                        // If the Target is reached\n                        if(t[0] == newR && t[1] == newC)  return step+1;\n                        \n                        // Put the new Box position into the queue along with the Player position\n                        queue.offer(new int[]{newR, newC,loc[0],loc[1]});\n                        visited[newR][newC][i] = true;\n                    }\n                }\n                \n                // Mark the Box position back to Floor\n                G[loc[0]][loc[1]] = \'.\';\n                \n                len--;\n            }\n            step++;\n        }\n        \n        // If the program reaches here, it means no solution.\n        return -1;\n    }\n    \n    // BFS for Plahyer\n    // This is just standard BFS, return true if Player can reach that position\n    private boolean reachable(int pR, int pC, int r, int c) {\n        // If the Play is on that position to start with, return true\n        if(pR == r && pC == c)  \n            return true;\n        Queue<int[]> queue = new LinkedList<>();\n        boolean[][] visited = new boolean[rows][cols];\n        queue.offer(new int[]{pR, pC});\n        \n        while(!queue.isEmpty()) {\n            int len = queue.size();\n            while(len > 0) {\n                int[] loc = queue.poll();\n                if(!visited[loc[0]][loc[1]]) {\n                    visited[loc[0]][loc[1]] = true;\n                    for(int i = 0; i < 4; i++) {\n                        int newR = loc[0] + dir[i];\n                        int newC = loc[1] + dir[i+1];\n                        if(inBound(newR,newC) \n                           && G[newR][newC] != \'#\' \n                           && !visited[newR][newC]) {\n                            if(r == newR && c == newC)  return true;\n                            queue.offer(new int[]{newR, newC});\n                        }\n                    }\n                }\n                len--;\n            }\n        }\n        return false;\n    }\n    \n    // Check if the coordinate is out of bound\n    private boolean inBound(int r, int c) {\n        return r >= 0 && c >= 0 && r < rows && c < cols;\n    }\n}\n```\n\nTime complexity: O((nm)^2)\nIn worse case, the Box has to traverse through the entire matrix which has nm vertices. We also need to do the same thing for the Play with each vertice. That makes the total iteration to be (nm)^2. But, in practice, it will be way lower than that.\n\nSpace complexity: O(nm)\nMemory needed for Queue in BFS.\n
['Breadth-First Search', 'Java']