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

😎 Решение:

import java.util.*;

public class Solution {
    public int minPushBox(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        Queue<int[]> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        int[] player = new int[2], box = new int[2], target = new int[2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'S') {
                    player = new int[]{i, j};
                } else if (grid[i][j] == 'B') {
                    box = new int[]{i, j};
                } else if (grid[i][j] == 'T') {
                    target = new int[]{i, j};
                }
            }
        }
        
        queue.offer(new int[]{player[0], player[1], box[0], box[1], 0});
        visited.add(player[0] + "," + player[1] + "," + box[0] + "," + box[1]);
        
        while (!queue.isEmpty()) {
            int[] state = queue.poll();
            int px = state[0], py = state[1], bx = state[2], by = state[3], pushes = state[4];
            if (bx == target[0] && by == target[1]) {
                return pushes;
            }
            for (int[] dir : directions) {
                int npx = px + dir[0], npy = py + dir[1];
                if (isValid(npx, npy, m, n, grid)) {
                    if (npx == bx && npy == by) {
                        int nbx = bx + dir[0], nby = by + dir[1];
                        if (isValid(nbx, nby, m, n, grid) && visited.add(npx + "," + npy + "," + nbx + "," + nby)) {
                            queue.offer(new int[]{npx, npy, nbx, nby, pushes + 1});
                        }
                    } else if (visited.add(npx + "," + npy + "," + bx + "," + by)) {
                        queue.offer(new int[]{npx, npy, bx, by, pushes});
                    }
                }
            }
        }
        
        return -1;
    }
    
    private boolean isValid(int x, int y, int m, int n, char[][] grid) {
        return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != '#';
    }
}

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