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

# Lets break the question into simple parts:

# Lets think that we have no person and we have to find the minimum path between box and the target. Easy right? Simple BFS.

# If you know how to solve the first part, what I actually do is modify first part with few constraints.

# I just check whether the box can be shifted to the new position(up, down, left, right)
# For it to be shifted to the new position the person has to be in a corresponding position right?
# So we check if the person can travel from his old position to his corresponding new position(using another BFS).
# If the person can travel to his new position than the box can be shifted, otherwise the box cannot be shifted.
# We keep repeating step 2 until we reach the target or it is not possible to move the box anymore.

# TC: O(M*N * M*N) = O(M^2 N^2)
# SC: O(M^2 N^2), since we are storing the state as box_pos + player_pos, there are M*N possibilities for each

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        M = len(grid)
        N = len(grid[0])

        for i in range(M):
            for j in range(N):
                c = grid[i][j]
                if c == 'T':
                    target = (i, j)
                elif c == 'B':
                    box = (i, j)
                elif c == 'S':
                    person = (i, j)


        # is this position an empty space in the grid?
        def isSpace(pos):
            row, col = pos[0], pos[1]
            return row >= 0 and row < M and col >= 0 and col < N and grid[row][col] != '#'

        # Can the player go from its current position to the destination? (player can't walk on the box)
        def playerCanVisit(playerPos, destination, box):
            q = deque([playerPos])
            visited = set()

            while q:
                pos = q.popleft()
                if pos == destination:
                    return True
                new_positions = [(pos[0]+1, pos[1]), (pos[0]-1, pos[1]), (pos[0], pos[1]+1), (pos[0], pos[1]-1)]
                for new_pos in new_positions:
                    if isSpace(new_pos) and new_pos != box and new_pos not in visited:
                        q.append(new_pos)
                        visited.add(new_pos)

            return False


        q = deque([(0, box, person)]) # distance travelled, box pos, player pos
        visited = set([box + person]) # box coordinate concat player coordinate defines a visited state

        while q:
            dist, box, player = q.popleft()
            if box == target:
                return dist

            # potential new box cooridnates
            box_coord = [(box[0]+1, box[1]), (box[0]-1, box[1]), (box[0], box[1]+1), (box[0], box[1]-1)]

            # positions player has to be in to push box to corresponding new coordinates
            player_coord = [(box[0]-1, box[1]), (box[0]+1, box[1]), (box[0], box[1]-1), (box[0], box[1]+1)]

            for new_box, player_pos in zip(box_coord, player_coord):
                if isSpace(new_box) and new_box+box not in visited:
                    if isSpace(player_pos) and playerCanVisit(player, player_pos, box):
                        q.append((dist+1, new_box, box))
                        visited.add(new_box + box)

        return -1