Python Dijkstra Short
edit: added an explanation below\nedit2: fixed a bug found by StefanPochmann@\n\n\ndef minPushBox(self, grid: List[List[str]]) -> int:\n    free = set((i, j) fo
edit: added an explanation below\nedit2: fixed a bug found by StefanPochmann@\n\n```\ndef minPushBox(self, grid: List[List[str]]) -> int:\n    free = set((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell != \'#\')\n    target = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == \'T\')\n    boxi, boxj = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == \'B\')\n    si, sj = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == \'S\')\n    visited = set()\n    heap = [(0, si, sj, boxi, boxj)]\n    while heap:\n        moves, si, sj, boxi, boxj = heapq.heappop(heap)\n        if (boxi, boxj) == target:\n            return moves\n        if (si, sj, boxi, boxj) in visited:\n            continue\n        visited.add((si, sj, boxi, boxj))\n        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n            ni, nj = si + dx, dy + sj\n            if (ni, nj) == (boxi, boxj) and (boxi + dx, boxj + dy) in free and (ni, nj, boxi + dx, boxj + dy) not in visited:\n                heapq.heappush(heap, (moves + 1, ni, nj, boxi + dx, boxj + dy))\n            elif (ni, nj) in free and (ni, nj) != (boxi, boxj) and (ni, nj, boxi, boxj) not in visited:\n                heapq.heappush(heap, (moves, ni, nj, boxi, boxj))\n    return -1\n```\n\nIn this solution, a Node is represented by the position of the box, and the position of the person i.e. ```(si, sj, boxi, boxj)```.\n\nTo find a Node\'s neighbors we add ```UP/DOWN/LEFT/RIGHT``` to the person\'s position and if the persons position ```==``` the boxes position, we also add this direction to the boxes position. The weight of the edge is ```1``` if the box moved,```0``` if not.\n\nWe could explicitly define ```Node, Edge, and Graph``` in the code, and even construct the whole graph prior to running Dijkstra, but it\'s easier and quicker to determine edge weights / neighbors by doing calculations on the ```(si, sj, boxi, boxj)``` tuple.\n\nNow we have our representations in place, just run Dijkstra in the normal way. I don\'t want to explain Dijkstra here, there are already really good explanations elsewhere.
[]