Standard BFS with Twist - Expand on Pushes, not Steps
Intuition\n Describe your first thoughts on how to solve this problem. \nA very conventional BFS algorithm with a small twist. Instead of always adding to the e
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nA very conventional BFS algorithm with a small twist. Instead of always adding to the end of the queue, we should prioritise nodes (greedily) with less steps and expand them first\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nAdd a state transition function: this generates the next shopkeep and box state from the current shopkeep and box state. \n\nIf the shopkeep moves in direction (x, y), and this movement coincides with the box, then it must be next to the box, and therefore will result in the box moving. In the latter case, we need to check if the box is OOB/hitting a `#`, otherwise we just check if the shopkeep is in a valid position.\n\nThen, just use a queue (Q) for the standard BFS, but append to the $$left$$ of the Q when we don\'t push the box, and append to the $right$ when we do. We then expand the least-pushed nodes first.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$O(n^4)$ - each state can hold the shopkeep in any position ($n^2$ positions) and the box in any position ($n^2$) positions, giving $n^2*n^2=n^4$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSame as time complexity - we may need to store all states\n\n# Code\n```\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n       dirs = [[-1, 0], [0, -1], [1, 0], [0, 1]]\n        M, N = len(grid), len(grid[0])\n\n        q = deque()\n        vis = set([(None, None)])\n\n        initMan, initBox = None, None\n\n        for i, r in enumerate(grid):\n            for j, c in enumerate(r):         \n                if c == "S":\n                    initMan = (i, j)\n                elif c == "B":\n                    initBox = (i, j)\n\n        q.append((initMan, initBox, 0))\n        \n        // returns newManPos, newBoxPos, numPushes\n        def getCoordChange(currMan, currBox, dirr):\n            mX, mY = currMan\n            bX, bY = currBox\n            dx, dy = dirr\n\n            nmX, nmY = mX + dx, mY + dy\n            if nmX == bX and nmY == bY: // man facing box\n                nbX, nbY = bX + dx, bY + dy // can box move??\n                if 0 <= nbX < M and 0 <= nbY < N and grid[nbX][nbY] != "#":\n                    return ((nmX, nmY), (nbX, nbY)), 1\n\n            elif 0 <= nmX < M and 0 <= nmY < N and grid[nmX][nmY] != "#":\n                return ((nmX, nmY), (bX, bY)), 0\n\n            // shopkeep neither in bounds nor facing box\n            return (None, None), -1\n\n\n        while q:\n            for _ in range(len(q)):\n                currMan, currBox, steps = q.popleft()\n\n                if grid[currBox[0]][currBox[1]] == "T":\n                    return steps\n                \n                for d in dirs:\n                    newState, push = getCoordChange(currMan, currBox, d)\n                    if newState in vis:\n                        continue\n                    vis.add(newState)\n                    nextState = (*newState, steps + push)\n                    // if we pushed, expand later\n                    if push == 1:\n                        q.append(nextState)\n                    // if we didn\'t push, expand sooner\n                    else:\n                        q.appendleft(nextState)\n\n        return -1\n\n```
['Python3']