A-star search
Heuristic (an under-estimate of the remaining moves required) is the Manhattan distance between box and target.\nA state consist of box and person locations tog
Heuristic (an under-estimate of the remaining moves required) is the Manhattan distance between box and target.\nA state consist of box and person locations together.\n\nRepeatedly pop the state with the lowest heuristic + previous moves off the heap.\nAttempt to move the person in all 4 directions.\nIf any direction moves the person to the box, check if the box can move to the nex position in the grid.\n\n```\n        rows, cols = len(grid), len(grid[0])\n        for r in range(rows):\n            for c in range(cols):\n                if grid[r][c] == "T":\n                    target = (r, c)\n                if grid[r][c] == "B":\n                    start_box = (r, c)\n                if grid[r][c] == "S":\n                    start_person = (r, c)\n                    \n        def heuristic(box):\n            return abs(target[0] - box[0]) + abs(target[1] - box[1])\n        \n        def out_bounds(location):  # return whether the location is in the grid and not a wall\n            r, c = location\n            if r < 0 or r >= rows:\n                return True\n            if c < 0 or c >= cols:\n                return True\n            return grid[r][c] == "#"\n                        \n        heap = [[heuristic(start_box), 0, start_person, start_box]]\n        visited = set()\n        \n        while heap:\n            _, moves, person, box = heapq.heappop(heap)\n            if box == target:\n                return moves\n            if (person, box) in visited: # do not visit same state again\n                continue\n            visited.add((person, box))\n            \n            for dr, dc in [[0, 1], [1, 0], [-1, 0], [0, -1]]:\n                new_person = (person[0] + dr, person[1] + dc)\n                if out_bounds(new_person):\n                    continue\n                    \n                if new_person == box:\n                    new_box = (box[0] + dr, box[1] + dc)\n                    if out_bounds(new_box):\n                        continue\n                    heapq.heappush(heap, [heuristic(new_box) + moves + 1, moves + 1, new_person, new_box])\n                else:\n                    heapq.heappush(heap, [heuristic(box) + moves, moves, new_person, box]) # box remains same\n        \n        return -1\n```
[]