Задача: 1263. Minimum Moves to Move a Box to Their Target Location
Сложность: hard

Кладовщик - это игра, в которой игрок перемещает коробки по складу, пытаясь доставить их в целевые места. Игра представлена сеткой символов m x n, где каждый элемент - это стена, пол или коробка. Ваша задача - переместить коробку "B" в целевую позицию "T" по следующим правилам: символ "S" представляет игрока. Игрок может перемещаться вверх, вниз, влево, вправо по сетке, если это пол (пустая клетка). Символ '.' обозначает пол, что означает свободную клетку для ходьбы. Символ '#' обозначает стену, что означает препятствие (туда невозможно пройти). В сетке есть только одна коробка 'B' и одна целевая клетка 'T'. Коробку можно переместить на соседнюю свободную клетку, стоя рядом с коробкой, а затем двигаясь в направлении коробки. Это толчок. Игрок не может пройти через коробку. Верните минимальное количество толчков, чтобы переместить коробку к цели. Если нет возможности добраться до цели, верните -1.

Пример:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3

👨‍💻 Алгоритм:

1⃣Выполните поиск в ширину (BFS) для всех возможных позиций игрока и коробки, отслеживая количество толчков.

2⃣Используйте очередь для хранения состояний игрока и коробки, а также текущего количества толчков.

3⃣Для каждого состояния проверяйте все возможные движения игрока и перемещения коробки, обновляйте очередь и отмечайте посещенные состояния.

😎 Решение:

from collections import deque

def minPushBox(grid):
    m, n = len(grid), len(grid[0])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    def valid(x, y):
        return 0 <= x < m and 0 <= y < n and grid[x][y] != '#'
    
    def bfs(start):
        queue = deque([start])
        visited = set([start])
        while queue:
            px, py, bx, by, pushes = queue.popleft()
            if (bx, by) == target:
                return pushes
            for dx, dy in directions:
                npx, npy = px + dx, py + dy
                if valid(npx, npy) and (npx, npy, bx, by, pushes) not in visited:
                    if (npx, npy) == (bx, by):
                        nbx, nby = bx + dx, by + dy
                        if valid(nbx, nby) and (npx, npy, nbx, nby, pushes + 1) not in visited:
                            queue.append((npx, npy, nbx, nby, pushes + 1))
                            visited.add((npx, npy, nbx, nby, pushes + 1))
                    else:
                        queue.append((npx, npy, bx, by, pushes))
                        visited.add((npx, npy, bx, by, pushes))
        return -1
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 'S':
                player = (i, j)
            elif grid[i][j] == 'B':
                box = (i, j)
            elif grid[i][j] == 'T':
                target = (i, j)
    
    return bfs((*player, *box, 0))

Ставь 👍 и забирай 📚 Базу знаний