Задача: 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⃣Для каждого состояния проверяйте все возможные движения игрока и перемещения коробки, обновляйте очередь и отмечайте посещенные состояния.

😎 Решение:

class Solution {
    fun minPushBox(grid: Array<CharArray>): Int {
        val m = grid.size
        val n = grid[0].size
        val directions = arrayOf(intArrayOf(-1, 0), intArrayOf(1, 0), intArrayOf(0, -1), intArrayOf(0, 1))
        
        fun isValid(x: Int, y: Int) = x in 0 until m && y in 0 until n && grid[x][y] != '#'
        
        var player = intArrayOf(0, 0)
        var box = intArrayOf(0, 0)
        var target = intArrayOf(0, 0)
        
        for (i in 0 until m) {
            for (j in 0 until n) {
                when (grid[i][j]) {
                    'S' -> player = intArrayOf(i, j)
                    'B' -> box = intArrayOf(i, j)
                    'T' -> target = intArrayOf(i, j)
                }
            }
        }
        
        val queue = ArrayDeque<IntArray>()
        val visited = mutableSetOf<String>()
        
        queue.addLast(intArrayOf(player[0], player[1], box[0], box[1], 0))
        visited.add("${player[0]},${player[1]},${box[0]},${box[1]}")
        
        while (queue.isNotEmpty()) {
            val (px, py, bx, by, pushes) = queue.removeFirst()
            if (bx == target[0] && by == target[1]) {
                return pushes
            }
            for ((dx, dy) in directions) {
                val npx = px + dx
                val npy = py + dy
                if (isValid(npx, npy)) {
                    if (npx == bx && npy == by) {
                        val nbx = bx + dx
                        val nby = by + dy
                        if (isValid(nbx, nby) && visited.add("$npx,$npy,$nbx,$nby")) {
                            queue.addLast(intArrayOf(npx, npy, nbx, nby, pushes + 1))
                        }
                    } else if (visited.add("$npx,$npy,$bx,$by")) {
                        queue.addLast(intArrayOf(npx, npy, bx, by, pushes))
                    }
                }
            }
        }
        
        return -1
    }
}

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