Java use 2 level BFS, beat 99%
It will be easy coming up with BFS. But some key point:\n1, you need to make sure Storekeeper:\na has room to push the box;\nb has a way to go to the room to pu
It will be easy coming up with BFS. But some key point:\n1, you need to make sure Storekeeper:\na has room to push the box;\nb has a way to go to the room to push the box. \nTherefore you need another bfs to find if the path exist;\n\n2 Make sure to set box as a blocker during bfs;\n\n3, Visited boolean array is tricky:\n2-d is not enough, some corner case:\nSenario 1, some push room is reachable if Storekeeper stands right, where another Senario 2, push room not reachable if Storekeeper stands right, though the postion of box are the same;\ntherefore, you need a 3-d array to mark box\' postion and another num to represents Storekeeper\'s postion compared to box(left, right, up, down);\n\n```\nclass Solution {\n    char[][] g;\n    int m, n;\n    int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};\n    public int minPushBox(char[][] grid) {\n        g = grid;\n        m = g.length; \n        n = g[0].length;\n        int step = 0;\n        boolean[][][] vs = new boolean[m][n][4];\n        \n        Queue<int[]> q = new LinkedList<>();\n        int[] st = new int[]{-1, -1}, ed = new int[]{-1, -1}, pl = new int[]{-1, -1};\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (g[i][j] == \'B\') st = new int[]{i, j};\n                if (g[i][j] == \'T\') ed = new int[]{i, j};\n                if (g[i][j] == \'S\') pl = new int[]{i, j};\n            }\n        }\n        q.offer(new int[]{st[0], st[1], pl[0], pl[1]});\n        while (!q.isEmpty()) {\n            for (int i = 0, l = q.size(); i < l; i++) {\n                int[] curr = q.poll();\n                if (curr[0] == ed[0] && curr[1] == ed[1]) return step;\n                for (int j = 0; j < dir.length; j++) {\n                    if (vs[curr[0]][curr[1]][j]) continue;\n                    int[] d = dir[j];\n                    int r0 = curr[0] + d[0], c0 = curr[1] + d[1];  // where pl stands, have room to push;\n                    if (r0 < 0 || r0 >= m || c0 < 0 || c0 >= n || g[r0][c0] == \'#\') continue;\n                    int r = curr[0] - d[0], c = curr[1] - d[1];  // box next spots;\n                    if (r < 0 || r >= m || c < 0 || c >= n || g[r][c] == \'#\') continue;\n                    if (!reachable(r0, c0, curr)) continue;\n                    vs[curr[0]][curr[1]][j] = true;\n                    q.offer(new int[]{r, c, curr[0], curr[1]});\n                }\n            }\n            step++;\n        }\n        return -1;\n    }\n    \n    private boolean reachable(int i, int j, int[] curr) {\n        Queue<int[]> q = new LinkedList<>();\n        q.offer(new int[]{curr[2], curr[3]});\n        boolean[][] vs = new boolean[m][n];\n        vs[curr[0]][curr[1]] = true;\n        while (!q.isEmpty()) {\n            int[] cur = q.poll();\n            if (cur[0] == i && cur[1] == j) return true;\n            for (int[] d : dir) {\n                int r = cur[0] - d[0], c = cur[1] - d[1];  // box next spots;\n                if (r < 0 || r >= m || c < 0 || c >= n || vs[r][c] || g[r][c] == \'#\') continue;\n                vs[r][c] = true;\n                q.offer(new int[]{r, c});\n            }\n        }\n        return false;\n    }\n}\n```
[]