推箱子

This solution uses a Breadth-First Search (BFS) approach to simulate the movement of both the player and the box in a grid-based puzzle game. The algorithm involves checking every possible movement of the box and corresponding positioning of the player necessary to push the box. For every box move, the player's ability to reach the position needed to make that push is verified through another BFS that takes into account the current box's position as an obstacle.

时间复杂度: O((m*n)^3)

空间复杂度: O((m*n)^2)

class Solution:

    def minPushBox(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])
        dirs = ((1, 0, -1, 0), (-1, 0, 1, 0), (0, -1, 0, 1), (0, 1, 0, -1))

        def check(start, target, bpos):
            if start == target: return True 
            tr, tc = target
            if not (rows > tr >= 0 <= tc < cols) or grid[tr][tc] == '#': return False
            q = deque([start])
            vis = {start, bpos}
            while q:
                r, c = q.popleft()
                for dr, dc, _, _ in dirs:
                    nr, nc = r + dr, c + dc
                    if rows > nr >= 0 <= nc < cols and (nr, nc) not in vis and grid[nr][nc] != '#':
                        if (nr, nc) == target:
                            return True
                        vis.add((nr, nc))
                        q.append((nr, nc))
            return False

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 'S':
                    s = (r, c)
                elif grid[r][c] == 'B':
                    b = (r, c)
                elif grid[r][c] == 'T':
                    t = (r, c)

        q = deque([(*b, *s)])
        vis = {(*b, *s)}
        step = 0
        while q:
            l = len(q)
            for _ in range(l):
                r, c, sr, sc = q.popleft()
                for dr, dc, dr2, dc2 in dirs:
                    nr, nc = r + dr, c + dc
                    nsr, nsc = r + dr2, c + dc2
                    if rows > nr >= 0 <= nc < cols and (nr, nc, nsr, nsc) not in vis and grid[nr][nc] != '#' and check((sr, sc), (nsr, nsc), (r, c)):
                        if (nr, nc) == t:
                            return step + 1
                        vis.add((nr, nc, nsr, nsc))
                        q.append((nr, nc, r, c))
            step += 1
        return -1