Кладовщик - это игра, в которой игрок перемещает коробки по складу, пытаясь доставить их в целевые места. Игра представлена сеткой символов m x n, где каждый element - это стена, пол или коробка. Ваша Problema - переместить коробку "B" в целевую позицию "T" по следующим правилам: символ "S" представляет игрока. Игрок может перемещаться вверх, вниз, влево, вправо по сетке, если это пол (пустая клетка). Символ '.' обозначает пол, что означает свободную клетку для ходьбы. Символ '#' обозначает стену, что означает препятствие (туда невозможно пройти). В сетке есть только одна коробка 'B' и одна целевая клетка 'T'. Коробку можно переместить на соседнюю свободную клетку, стоя рядом с коробкой, а затем двигаясь в направлении коробки. Это толчок. Игрок не может пройти через коробку. return минимальное количество толчков, чтобы переместить коробку к цели. Если нет возможности добраться до цели, return -1.
Esempio:
Input: grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#",".","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output: 3
C# soluzione
abbinato/originaleusing 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++ soluzione
bozza automatica, rivedere prima dell'invio#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 soluzione
abbinato/originaleimport 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 soluzione
abbinato/originalefrom 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))Algorithm
Выполните Breadth-first search (BFS) для всех возможных позиций игрока и коробки, отслеживая количество толчков.
Используйте очередь для хранения состояний игрока и коробки, а также текущего количества толчков.
Для каждого состояния проверяйте все возможные движения игрока и перемещения коробки, обновляйте очередь и отмечайте посещенные состояния.
😎
Vacancies for this task
offerte attive with overlapping task tags are mostrati.