Python 0-1 BFS, Straightforward
Intuition / Approach\nWe can view this problem is a state-space single source shortest path (SSSP) problem.\n\nWe formulate each state as a tuple $(r, c, x, y)$
# Intuition / Approach\nWe can view this problem is a state-space single source shortest path (SSSP) problem.\n\nWe formulate each state as a tuple $(r, c, x, y)$ where $(r,c)$ is the position of the player and $(x, y)$ is the position of the box.\n- The initial state is $(r, c, x, y)$ where `grid[r][c] = "S"` and `grid[x][y] = "B"`\n- The initial state is any $(r, c, x, y)$ where `grid[x][y] = "T"`\n\nThe edges of the graph between each state correspond to the character walking in one of the NSEW directions. \n- If the player doesn\'t push the box, cost 0\n- If the player pushes the box, cost 1\n\nSince the costs are 0 and 1, we can just do 0-1 BFS rather than Dijkstra. We maintain a deque of frontier nodes to explore and expand.\n- If the step cost 0, we push to the front of the deque\n- If the step cost 1, we push to the back of the deque\n- This ensures that the deque is always sorted by the cost of state and that we will exhaust all the states of distance $i$ before moving to states of distance $i+1$, ensuring correctness\n\n\n# Complexity\n- Time complexity: $O(H^2 W^2)$\n\n- Space complexity: $O(H^2 W^2)$\n\n# Code\n```\nfrom collections import deque \nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        h = len(grid)\n        w = len(grid[0])\n\n        sr, sc = -1, -1\n        tr, tc = -1, -1\n        pr, pc = -1, -1\n        for r in range(h):\n            for c in range(w):\n                if grid[r][c] == \'S\':\n                    pr, pc = r, c\n                    grid[r][c] = \'.\'\n                elif grid[r][c] == \'B\':\n                    sr, sc = r, c\n                    grid[r][c] = \'.\'\n                elif grid[r][c] == \'T\':\n                    tr, tc = r, c\n                    grid[r][c] == \'.\'\n\n        assert -1 not in {tr, tc, sr, sc, pr, pc}\n\n        q = deque([(pr, pc, sr, sc)]) # (player row, player col, box row, box col)\n        \n        dist = {(pr, pc, sr, sc): 0}\n        dr = [-1, 1, 0, 0]\n        dc = [0, 0, 1, -1]\n\n        def valid(r, c):\n            if r >= h or r < 0 or c >= w or c < 0: return False # out of grid\n            if grid[r][c] == "#": return False # impossible\n            return True\n\n        while len(q) > 0:\n            state = q[0]\n            q.popleft()\n\n            r, c, br, bc = state\n            print(state)\n            if br == tr and bc == tc:\n                return dist[state]\n\n            for i in range(4):\n                nr, nc = r + dr[i], c + dc[i]\n\n                if not valid(nr, nc): continue\n                if (nr, nc) == (br, bc):\n                    # check if box can be moved\n                    nbr, nbc = br + dr[i], bc + dc[i]\n                    if not valid(nbr, nbc): continue\n                    push = True\n                else:\n                    nbr, nbc = br, bc\n                    push = False\n                \n                newState = (nr, nc, nbr, nbc)\n                if newState in dist: continue\n                \n                if push:\n                    dist[newState] = dist[state] + 1\n                    q.append(newState)\n                else:\n                    dist[newState] = dist[state]\n                    q.appendleft(newState)\n\n        return -1\n```
['Python3']