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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int MinPushBox(char[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int[][] directions = new int[][] {
            new int[] {-1, 0}, new int[] {1, 0}, new int[] {0, -1}, new int[] {0, 1}
        };
        
        Func<int, int, bool> isValid = (x, y) => x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != '#';
        
        int px = 0, py = 0, bx = 0, by = 0, tx = 0, ty = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'S') {
                    px = i;
                    py = j;
                } else if (grid[i][j] == 'B') {
                    bx = i;
                    by = j;
                } else if (grid[i][j] == 'T') {
                    tx = i;
                    ty = j;
                }
            }
        }
        
        Queue<int[]> queue = new Queue<int[]>();
        HashSet<string> visited = new HashSet<string>();
        
        queue.Enqueue(new int[] {px, py, bx, by, 0});
        visited.Add($"{px},{py},{bx},{by}");
        
        while (queue.Count > 0) {
            int[] state = queue.Dequeue();
            int px = state[0], py = state[1], bx = state[2], by = state[3], pushes = state[4];
            if (bx == tx && by == ty) {
                return pushes;
            }
            foreach (var dir in directions) {
                int npx = px + dir[0], npy = py + dir[1];
                if (isValid(npx, npy)) {
                    if (npx == bx && npy == by) {
                        int nbx = bx + dir[0], nby = by + dir[1];
                        if (isValid(nbx, nby) && visited.Add($"{npx},{npy},{nbx},{nby}")) {
                            queue.Enqueue(new int[] {npx, npy, nbx, nby, pushes + 1});
                        }
                    } else if (visited.Add($"{npx},{npy},{bx},{by}")) {
                        queue.Enqueue(new int[] {npx, npy, bx, by, pushes});
                    }
                }
            }
        }
        
        return -1;
    }
}

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