BFS with (box,player) as state
This problem involves regular BFS with a few important distinctions.\n1. We cannot just directly look for shortest path from box to target. An additional condit
This problem involves regular BFS with a few important distinctions.\n1. We cannot just directly look for shortest path from box to target. An additional condition is that the player should be able to reach the push_spot from where the box can be pushed. This extra condition needs to be checked at each step before considering a box in our BFS traversal.\n2. The way we consider visited set changes slightly. It is not just the posiiton of the box that matters but also the player. There are some cases where a box needs to be pushed past a position and then pushed back into it to allow the player to reach the push spots. \n3. In terms of implementation, it is easier if we maintain the positions of box and player outside the grid, in two variables. This is because we evaluate several options, and maintaing the box and player within the grid can get messy\n\nSo overall, this problem can be solved by taking(box, player) as state and checking if player can reach the push_spot\n```\nfrom collections import deque\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        box, player = None, None\n        for r in range(len(grid)):\n            for c in range(len(grid[0])):\n                if grid[r][c] == "S":\n                    player = (r,c)\n                    grid[r][c] = "."\n                elif grid[r][c] == "B":\n                    box = (r, c)\n                    grid[r][c] = "."\n        \n        def get_neighbours_for_box(box, grid):\n            moves = [(0,-1),(0,1),(-1,0),(1,0)]\n            r,c = box[0], box[1]\n            neighbours = []\n            for m in moves:\n                n_r, n_c = r + m[0], c + m[1]\n                push_spot = r - m[0], c - m[1]\n                if 0 <= n_r < len(grid) and 0 <= n_c < len(grid[0]) and grid[n_r][n_c] not in ["#"] and 0 <= push_spot[0] < len(grid) and 0 <= push_spot[1] < len(grid[0]) and grid[push_spot[0]][push_spot[1]] not in ["#"]:\n                    neighbours.append(((n_r, n_c), push_spot))\n            return neighbours\n        \n        def get_neighbours_for_player(player, box, grid):\n            moves = [(0,-1),(0,1),(-1,0),(1,0)]\n            r,c = player[0], player[1]\n            neighbours = []\n            for m in moves:\n                n_r, n_c = r + m[0], c + m[1]\n                if 0 <= n_r < len(grid) and 0 <= n_c < len(grid[0]) and grid[n_r][n_c] not in ["#"] and (n_r,n_c) != box:\n                    neighbours.append((n_r, n_c))\n            return neighbours\n        \n        def player_can_reach(player, push_spot, box, grid):\n            queue = deque()\n            queue.append(player)\n            visited = set()\n            visited.add(player)\n            while queue:\n                p = queue.popleft()\n                if p == push_spot:\n                    return True\n                for n in get_neighbours_for_player(p, box, grid):\n                    if n not in visited:\n                        visited.add(n)\n                        queue.append(n)\n            return False\n        \n        queue = deque()\n        visited = set()\n        visited.add((box,player))\n        queue.append((box, player, 0))\n        while queue:\n            box,player,d = queue.popleft()\n            if grid[box[0]][box[1]] == "T":\n                return d\n            neighbours = get_neighbours_for_box(box, grid)\n            for n, ps in neighbours:\n                if (n,box) not in visited and player_can_reach(player, ps, box, grid):\n                    visited.add((n,box))\n                    queue.append((n,box,d+1))\n        return -1\n\t\t```
[]