Leetcode 1263. Minimum Moves to Move a Box to Their Target Location

Problem statement

https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/

Solution

The idea is to use bfs where we have states (S_x, S_y, B_x, B_y) When we move box, we add element to the end of queue, when we just move person without box, we add to the start of the queue. Actually what we have here we can call it 0-1 bfs approach.

Complexity

Time complexity is O(n^2m^2).

Code

class Solution:
    def minPushBox(self, grid):
        def check(x, y): return 0 <= x < n and 0 <= y < m and grid[y][x] != "#"
        
        m, n, v = len(grid), len(grid[0]), set()
        neibs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        
        for x, y in product(range(n), range(m)):
            if grid[y][x] == "B": B = (x, y)
            if grid[y][x] == "S": S = (x, y)
        
        Q = deque([(0,) + S + B])
                
        while Q:
            steps, Sx, Sy, Bx, By = Q.popleft()
            if grid[By][Bx] == "T": return steps
            
            for dx, dy in neibs:
                if check(Sx+dx, Sy +dy) and (Sx+dx, Sy+dy) != (Bx, By):
                    new = (Sx+dx, Sy+dy, Bx, By)
                    if new not in v:
                        v.add(new)
                        Q.appendleft((steps,) + new)
            
            if abs(Sx - Bx) + abs(Sy - By) == 1:  #move box
                if check(2*Bx-Sx, 2*By-Sy):
                    new = (Bx, By, 2*Bx - Sx, 2*By - Sy)
                    if new not in v:
                        v.add(new)
                        Q.append((steps + 1,) + new) 
        
        return -1

Remark

There is also approach using Dijkstra algorithm.