← Static tasks

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

leetcode hard

#array#csharp#graph#hard#hash-table#leetcode#matrix#queue#search#string

Task

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

Пример:

Input: grid = [["#","#","#","#","#","#"],

["#","T","#","#","#","#"],

["#",".",".","B",".","#"],

["#",".","#","#",".","#"],

["#",".",".",".","S","#"],

["#","#","#","#","#","#"]]

Output: 3

C# solution

matched/original
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;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinPushBox(char[][] grid) {
        int m = grid.size(), n = grid[0].size();
        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.push_back($"{px},{py},{bx},{by}");
        
        while (queue.size() > 0) {
            vector<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.push_back($"{npx},{npy},{nbx},{nby}")) {
                            queue.Enqueue(new int[] {npx, npy, nbx, nby, pushes + 1});
                        }
                    } else if (visited.push_back($"{npx},{npy},{bx},{by}")) {
                        queue.Enqueue(new int[] {npx, npy, bx, by, pushes});
                    }
                }
            }
        }
        
        return -1;
    }
}

Java solution

matched/original
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] != '#';
    }
}

Python solution

matched/original
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))

Explanation

Algorithm

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

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

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

😎