Java straightforward BFS solution
For me, this is a typical bfs question to find the minimum step, so the key point is to find out the state. For this problem, I choose the coordinates of box an
For me, this is a typical bfs question to find the minimum step, so the key point is to find out the state. For this problem, I choose the coordinates of box and storekeeper as the state. Because the grid length is from 1 to 20, we can use one 32 bit integer to present all the coordinates.\nEvery step, move storekeeper 1 step, if it meet the box, then the box move 1 step in the same direction. Because it want to know the minimum step the box move, so when the first time box on the target pocision, it may not be the minimum anwser. So we compare every one and find the minimum step.\n\n```java\nclass Solution {\n    int[][] moves = new int[][]{{0,-1}, {0,1}, {-1,0}, {1,0}};\n    public int minPushBox(char[][] grid) {\n        int[] box = null, target = null, storekeeper = null;\n        int n = grid.length, m = grid[0].length;\n        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {\n            if (grid[i][j] == \'B\') box = new int[]{i, j};\n            else if (grid[i][j] == \'T\') target = new int[]{i, j};\n            else if (grid[i][j] == \'S\') storekeeper = new int[]{i, j};\n        }\n        Queue<Integer> q = new LinkedList<>();\n        Map<Integer, Integer> dis = new HashMap<>();\n        int start = encode(box[0], box[1], storekeeper[0], storekeeper[1]);\n        dis.put(start, 0);\n        q.offer(start);\n        int ret = Integer.MAX_VALUE;\n        while (!q.isEmpty()) {\n            int u = q.poll();\n            int[] du = decode(u);\n            if (dis.get(u) >= ret) continue;\n            if (du[0] == target[0] && du[1] == target[1]) {\n                ret = Math.min(ret, dis.get(u));\n                continue;\n            }\n            int[] b = new int[]{du[0], du[1]};\n            int[] s = new int[]{du[2], du[3]};\n\t\t\t// move the storekeeper for 1 step\n            for (int[] move : moves) {\n                int nsx = s[0] + move[0];\n                int nsy = s[1] + move[1];\n                if (nsx < 0 || nsx >= n || nsy < 0 || nsy >= m || grid[nsx][nsy] == \'#\') continue;\n\t\t\t\t// if it meet the box, then the box move in the same direction\n                if (nsx == b[0] && nsy == b[1]) {\n                    int nbx = b[0] + move[0];\n                    int nby = b[1] + move[1];\n                    if (nbx < 0 || nbx >= n || nby < 0 || nby >= m || grid[nbx][nby] == \'#\') continue;\n                    int v = encode(nbx, nby, nsx, nsy);\n                    if (dis.containsKey(v) && dis.get(v) <= dis.get(u) + 1) continue;\n                    dis.put(v, dis.get(u) + 1);\n                    q.offer(v);\n                } else { // if the storekeeper doesn\'t meet the box, the position of the box do not change\n                    int v = encode(b[0], b[1], nsx, nsy);\n                    if (dis.containsKey(v) && dis.get(v) <= dis.get(u)) continue;\n                    dis.put(v, dis.get(u));\n                    q.offer(v);\n                }\n            }\n        }\n        return ret == Integer.MAX_VALUE ? -1 : ret;\n    }\n    int encode(int bx, int by, int sx, int sy) {\n        return (bx << 24) | (by << 16) | (sx << 8) | sy;\n    }\n    int[] decode(int num) {\n        int[] ret = new int[4];\n        ret[0] = (num >>> 24) & 0xff;\n        ret[1] = (num >>> 16) & 0xff;\n        ret[2] = (num >>> 8) & 0xff;\n        ret[3] = num & 0xff;\n        return ret;\n    }\n}\n```
[]