Python Dijkstra (player and box coordinates - state space)
If state space (vertices of a graph) represented as player and box coordinates, and the edges have value 1 if during state transition we pushed the box, 0 other
If state space (vertices of a graph) represented as player and box coordinates, and the edges have value 1 if during state transition we pushed the box, 0 otherwise. Given this formulation we can run Dijkstra algorithm to find minimum number of pushes to get box to the target.\n\n```\nfrom sortedcontainers import SortedList\n\nclass Solution:\n    def minPushBox(self, grid):\n        n = len(grid)\n        m = len(grid[0])\n\n        player, box, target = (0, 0), (0, 0), (0, 0)\n        for i in range(n):\n            for j in range(m):\n                if grid[i][j] == \'S\':\n                    player = (i, j)\n                if grid[i][j] == \'T\':\n                    target = (i, j)\n                if grid[i][j] == \'B\':\n                    box = (i, j)\n\n        def get_nbs(p):\n            x, y = p\n            return [(dx, dy) for dx, dy in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]\n                    if 0 <= dx < n and 0 <= dy < m and grid[dx][dy] != \'#\']\n\n        def get_next_state(state):\n            p, b = state\n\n            next_states = []\n            for dp in get_nbs(p):\n                if dp != b:\n                    next_states.append((0, dp, b))\n                else:\n                    dx = dp[0] - p[0]\n                    dy = dp[1] - p[1]\n                    db = (b[0] + dx, b[1] + dy)\n                    if 0 <= db[0] < n and 0 <= db[1] < m and grid[db[0]][db[1]] != \'#\':\n                        next_states.append((1, dp, db))\n            return next_states\n\n        start = (player, box)\n        q = SortedList([(0, start)])\n        attended = set()\n\n        while len(q):\n            d, state = q.pop(0)\n            if state in attended: continue\n            attended.add(state)\n            if state[1] == target:\n                return d\n\n            for ns in get_next_state(state):\n                if ns[1:] not in attended:\n                    q.add((d + ns[0], ns[1:]))\n        return -1\n```
[]