LC [H] 1263 Minimum Moves to Move a Box to Their Target Location - ALawliet/algorithms GitHub Wiki

trick: for the player to move the box, they have to move into the box location, then push the box that same direction

  1. find initial locations
  2. heuristic function
  3. out of bounds function
  4. min priority queue with states (heuristic + prev moves, prev moves, player location, box location)
  5. BFS, goal checks, 2 cases moving player into box or not, updating heuristic
h(heuristic) = manhattan distance + number of previous moves
g(cost) = 1
f = h + g
minimize f

from queue import PriorityQueue

DIRS = [(0,1), (1,0), (-1,0), (0,-1)]

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        # find the initial locations
        n_rows, n_cols = len(grid), len(grid[0])
        for r in range(n_rows):
            for c in range(n_cols):
                if grid[r][c] == 'T':
                    target = (r, c)
                if grid[r][c] == 'B':
                    start_box = (r, c)
                if grid[r][c] == 'S':
                    start_person = (r, c)
                    
        def h(box, moves=0):
            return abs(target[0] - box[0]) + abs(target[1] - box[1]) + moves
        
        def oob(location):  # return whether the location is in the grid and not a wall
            r, c = location
            return r < 0 or r >= n_rows or c < 0 or c >= n_cols or grid[r][c] == '#' # else '.' ok
                        
        # heuristic, number of previous moves, person location, box location
        # H = heuristic + number of previous moves
        minPQ = PriorityQueue()
        minPQ.put( (h(start_box, 0), 0, start_person, start_box) )
        visited = set()
        
        while not minPQ.empty():
            # BFS checks goal first
            _, moves, person, box = minPQ.get()
            
            if box == target: return moves # done, box moved to target
            
            if (person, box) in visited: continue # don't revisit same state

            # then adds visited
            visited.add( (person, box) )
            
            for dr, dc in DIRS:
                next_person = (person[0] + dr, person[1] + dc)
                
                if oob(next_person): continue
                                        
                # to move the box, the player must end up where the box is after a push
                if next_person == box: # if player moves into box
                    # then try to move the box in same direction (doesn't require another loop)
                    next_box = (box[0] + dr, box[1] + dc)
                    
                    if oob(next_box): continue
                    
                    # f = h + g, g = 1
                    minPQ.put( (h(next_box, moves) + 1, moves + 1, next_person, next_box) )
                else:
                    # person moves, box remains same
                    # f = h
                    minPQ.put( (h(box, moves), moves, next_person, box) )
        
        return -1

footer

⚠️ **GitHub.com Fallback** ⚠️