Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1263.html
1263. Minimum Moves to Move a Box to Their Target Location (Hard)
Storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations.
The game is represented by a grid
of size m x n
, where each element is a wall, floor, or a box.
Your task is move the box 'B'
to the target position 'T'
under the following rules:
- Player is represented by character
'S'
and can move up, down, left, right in thegrid
if it is a floor (empy cell). - Floor is represented by character
'.'
that means free cell to walk. - Wall is represented by character
'#'
that means obstacle (impossible to walk there). - There is only one box
'B'
and one target cell'T'
in thegrid
. - The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push.
- The player cannot walk through the box.
Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1
.
Example 1:
Input: grid = [["#","#","#","#","#","#"], ["#","T","#","#","#","#"], ["#",".",".","B",".","#"], ["#",".","#","#",".","#"], ["#",".",".",".","S","#"], ["#","#","#","#","#","#"]] Output: 3 Explanation: We return only the number of times the box is pushed.
Example 2:
Input: grid = [["#","#","#","#","#","#"], ["#","T","#","#","#","#"], ["#",".",".","B",".","#"], ["#","#","#","#",".","#"], ["#",".",".",".","S","#"], ["#","#","#","#","#","#"]] Output: -1
Example 3:
Input: grid = [["#","#","#","#","#","#"], ["#","T",".",".","#","#"], ["#",".","#","B",".","#"], ["#",".",".",".",".","#"], ["#",".",".",".","S","#"], ["#","#","#","#","#","#"]] Output: 5 Explanation: push the box down, left, left, up and up.
Example 4:
Input: grid = [["#","#","#","#","#","#","#"], ["#","S","#",".","B","T","#"], ["#","#","#","#","#","#","#"]] Output: -1
Constraints:
m == grid.length
n == grid[i].length
1 <= m <= 20
1 <= n <= 20
grid
contains only characters'.'
,'#'
,'S'
,'T'
, or'B'
.- There is only one character
'S'
,'B'
and'T'
in thegrid
.
Related Topics: Breadth-first Search
Solution 1. BFS + DP
dp[sx][sy][bx][by]
is the minimal number of pushes needed to make S
at (sx, sy)
and B
at (bx, by)
.
// OJ: https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/
// Time: O((MN)^2)
// Space: O((MN)^2)
class Solution {
public:
int minPushBox(vector<vector<char>>& G) {
int dp[20][20][20][20] = {}, M = G.size(), N = G[0].size(), sx, sy, bx, by, tx, ty, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }, ans = INT_MAX;
memset(dp, 0x3f, sizeof(dp));
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (G[i][j] == 'S') sx = i, sy = j;
else if (G[i][j] == 'B') bx = i, by = j;
else if (G[i][j] == 'T') tx = i, ty = j;
}
}
queue<vector<int>> q;
q.push({ sx, sy, bx, by, 0 });
dp[sx][sy][bx][by] = 0;
while (q.size()) {
auto v = q.front();
q.pop();
int sx = v[0], sy = v[1], bx = v[2], by = v[3], push = v[4];
if (bx == tx && by == ty) ans = min(ans, push);
for (auto [dx, dy] : dirs) {
int x = sx + dx, y = sy + dy;
if (x < 0 || y < 0 || x >= M || y >= N || G[x][y] == '#') continue;
int bx2 = bx, by2 = by, push2 = push;
if (x == bx && y == by) bx2 += dx, by2 += dy, ++push2;
if (bx2 < 0 || by2 < 0 || bx2 >= M || by2 >= N || G[bx2][by2] == '#' || push2 >= dp[x][y][bx2][by2]) continue;
dp[x][y][bx2][by2] = push2;
q.push({ x, y, bx2, by2, push2 });
}
}
return ans == INT_MAX ? -1 : ans;
}
};
-
class Solution { public int minPushBox(char[][] grid) { final int BLOCK = -1; final int WHITE = 0; final int GRAY = 1; final int BLACK = 2; int rows = grid.length, columns = grid[0].length; int[][][][] colors = new int[rows][columns][rows][columns]; int[][][][] distances = new int[rows][columns][rows][columns]; for (int bRow = 0; bRow < rows; bRow++) { for (int bCol = 0; bCol < columns; bCol++) { for (int pRow = 0; pRow < rows; pRow++) { for (int pCol = 0; pCol < columns; pCol++) distances[bRow][bCol][pRow][pCol] = Integer.MAX_VALUE; } } } for (int bRow = 0; bRow < rows; bRow++) { for (int bCol = 0; bCol < columns; bCol++) { for (int pRow = 0; pRow < rows; pRow++) { for (int pCol = 0; pCol < columns; pCol++) { if (grid[bRow][bCol] == '#' || grid[pRow][pCol] == '#') { colors[bRow][bCol][pRow][pCol] = BLOCK; distances[bRow][bCol][pRow][pCol] = -1; } } } } } int initialBoxRow = -1, initialBoxColumn = -1, initialPlayerRow = -1, initialPlayerColumn = -1, targetRow = -1, targetColumn = -1; int count = 0; outer: for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { char c = grid[i][j]; if (c == 'B') { initialBoxRow = i; initialBoxColumn = j; count++; } else if (c == 'S') { initialPlayerRow = i; initialPlayerColumn = j; count++; } else if (c == 'T') { targetRow = i; targetColumn = j; count++; } if (count == 3) break outer; } } int[][] directions = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} }; distances[initialBoxRow][initialBoxColumn][initialPlayerRow][initialPlayerColumn] = 0; PriorityQueue<Status> queue = new PriorityQueue<Status>(); queue.offer(new Status(initialBoxRow, initialBoxColumn, initialPlayerRow, initialPlayerColumn, 0)); while (!queue.isEmpty()) { Status status = queue.poll(); int boxRow = status.boxRow, boxColumn = status.boxColumn, playerRow = status.playerRow, playerColumn = status.playerColumn, distance = status.distance; for (int[] direction : directions) { int playerNewRow = playerRow + direction[0], playerNewColumn = playerColumn + direction[1]; if (playerNewRow < 0 || playerNewRow >= rows || playerNewColumn < 0 || playerNewColumn >= columns || grid[playerNewRow][playerNewColumn] == '#') continue; if (playerNewRow == boxRow && playerNewColumn == boxColumn) { int boxNewRow = boxRow + direction[0], boxNewColumn = boxColumn + direction[1]; if (boxNewRow < 0 || boxNewRow >= rows || boxNewColumn < 0 || boxNewColumn >= columns || grid[boxNewRow][boxNewColumn] == '#') continue; if (boxNewRow == targetRow && boxNewColumn == targetColumn) return distance + 1; else if (colors[boxNewRow][boxNewColumn][playerNewRow][playerNewColumn] == WHITE) { colors[boxNewRow][boxNewColumn][playerNewRow][playerNewColumn] = GRAY; distances[boxNewRow][boxNewColumn][playerNewRow][playerNewColumn] = distance + 1; queue.offer(new Status(boxNewRow, boxNewColumn, playerNewRow, playerNewColumn, distance + 1)); } } else { if (colors[boxRow][boxColumn][playerNewRow][playerNewColumn] == WHITE) { colors[boxRow][boxColumn][playerNewRow][playerNewColumn] = GRAY; distances[boxRow][boxColumn][playerNewRow][playerNewColumn] = distance; queue.offer(new Status(boxRow, boxColumn, playerNewRow, playerNewColumn, distance)); } } } colors[boxRow][boxColumn][playerRow][playerColumn] = BLACK; } int totalDistance = Integer.MAX_VALUE; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { int distance = distances[targetRow][targetColumn][i][j]; totalDistance = Math.min(totalDistance, distance); } } return totalDistance; } } class Status implements Comparable<Status> { int boxRow; int boxColumn; int playerRow; int playerColumn; int distance; public Status() { } public Status(int boxRow, int boxColumn, int playerRow, int playerColumn, int distance) { this.boxRow = boxRow; this.boxColumn = boxColumn; this.playerRow = playerRow; this.playerColumn = playerColumn; this.distance = distance; } public int compareTo(Status status2) { return this.distance - status2.distance; } }
-
// OJ: https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/ // Time: O((MN)^2) // Space: O((MN)^2) class Solution { public: int minPushBox(vector<vector<char>>& A) { int M = A.size(), N = A[0].size(), tx, ty, sx, sy, bx, by, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }, dp[20][20][20][20] = {}, ans = INT_MAX; for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { if (A[i][j] == 'S') sx = i, sy = j; else if (A[i][j] == 'B') bx = i, by = j; else if (A[i][j] == 'T') tx = i, ty = j; } } memset(dp, 0x3f, sizeof(dp)); dp[sx][sy][bx][by] = 0; queue<array<int, 4>> q{ { {sx, sy, bx, by} } }; while (q.size()) { auto [sx, sy, bx, by] = q.front(); q.pop(); int step = dp[sx][sy][bx][by]; if (bx == tx && by == ty) ans = min(ans, step); for (auto &[dx, dy] : dirs) { int a = sx + dx, b = sy + dy, bx2 = bx, by2 = by, step2 = step; if (a < 0 || a >= M || b < 0 || b >= N || A[a][b] == '#') continue; if (a == bx && b == by) bx2 += dx, by2 += dy, step2++; if (bx2 < 0 || bx2 >= M || by2 < 0 || by2 >= N || A[bx2][by2] == '#' || step2 >= dp[a][b][bx2][by2]) continue; dp[a][b][bx2][by2] = step2; q.push({a, b, bx2, by2}); } } return ans == INT_MAX ? -1 : ans; } };
-
class Solution: def minPushBox(self, grid: List[List[str]]) -> int: def f(i: int, j: int) -> int: return i * n + j def check(i: int, j: int) -> bool: return 0 <= i < m and 0 <= j < n and grid[i][j] != "#" for i, row in enumerate(grid): for j, c in enumerate(row): if c == "S": si, sj = i, j elif c == "B": bi, bj = i, j m, n = len(grid), len(grid[0]) dirs = (-1, 0, 1, 0, -1) q = deque([(f(si, sj), f(bi, bj), 0)]) vis = [[False] * (m * n) for _ in range(m * n)] vis[f(si, sj)][f(bi, bj)] = True while q: s, b, d = q.popleft() bi, bj = b // n, b % n if grid[bi][bj] == "T": return d si, sj = s // n, s % n for a, b in pairwise(dirs): sx, sy = si + a, sj + b if not check(sx, sy): continue if sx == bi and sy == bj: bx, by = bi + a, bj + b if not check(bx, by) or vis[f(sx, sy)][f(bx, by)]: continue vis[f(sx, sy)][f(bx, by)] = True q.append((f(sx, sy), f(bx, by), d + 1)) elif not vis[f(sx, sy)][f(bi, bj)]: vis[f(sx, sy)][f(bi, bj)] = True q.appendleft((f(sx, sy), f(bi, bj), d)) return -1
-
func minPushBox(grid [][]byte) int { m, n := len(grid), len(grid[0]) var si, sj, bi, bj int for i, row := range grid { for j, c := range row { if c == 'S' { si, sj = i, j } else if c == 'B' { bi, bj = i, j } } } f := func(i, j int) int { return i*n + j } check := func(i, j int) bool { return i >= 0 && i < m && j >= 0 && j < n && grid[i][j] != '#' } q := [][]int{[]int{f(si, sj), f(bi, bj), 0} } vis := make([][]bool, m*n) for i := range vis { vis[i] = make([]bool, m*n) } vis[f(si, sj)][f(bi, bj)] = true dirs := [5]int{-1, 0, 1, 0, -1} for len(q) > 0 { p := q[0] q = q[1:] si, sj, bi, bj = p[0]/n, p[0]%n, p[1]/n, p[1]%n d := p[2] if grid[bi][bj] == 'T' { return d } for k := 0; k < 4; k++ { sx, sy := si+dirs[k], sj+dirs[k+1] if !check(sx, sy) { continue } if sx == bi && sy == bj { bx, by := bi+dirs[k], bj+dirs[k+1] if !check(bx, by) || vis[f(sx, sy)][f(bx, by)] { continue } vis[f(sx, sy)][f(bx, by)] = true q = append(q, []int{f(sx, sy), f(bx, by), d + 1}) } else if !vis[f(sx, sy)][f(bi, bj)] { vis[f(sx, sy)][f(bi, bj)] = true q = append([][]int{[]int{f(sx, sy), f(bi, bj), d} }, q...) } } } return -1 }
-
function minPushBox(grid: string[][]): number { const [m, n] = [grid.length, grid[0].length]; let [si, sj, bi, bj] = [0, 0, 0, 0]; for (let i = 0; i < m; ++i) { for (let j = 0; j < n; ++j) { if (grid[i][j] === 'S') { [si, sj] = [i, j]; } else if (grid[i][j] === 'B') { [bi, bj] = [i, j]; } } } const f = (i: number, j: number): number => i * n + j; const check = (i: number, j: number): boolean => i >= 0 && i < m && j >= 0 && j < n && grid[i][j] !== '#'; const q: Deque<[number, number, number]> = new Deque(); const vis: boolean[][] = new Array(m * n) .fill(0) .map(() => new Array(m * n).fill(false)); q.push([f(si, sj), f(bi, bj), 0]); vis[f(si, sj)][f(bi, bj)] = true; const dirs: number[] = [-1, 0, 1, 0, -1]; while (q.size() > 0) { const [s, b, d] = q.shift()!; const [si, sj] = [Math.floor(s / n), s % n]; const [bi, bj] = [Math.floor(b / n), b % n]; if (grid[bi][bj] === 'T') { return d; } for (let k = 0; k < 4; ++k) { const [sx, sy] = [si + dirs[k], sj + dirs[k + 1]]; if (!check(sx, sy)) { continue; } if (sx === bi && sy === bj) { const [bx, by] = [bi + dirs[k], bj + dirs[k + 1]]; if (!check(bx, by) || vis[f(sx, sy)][f(bx, by)]) { continue; } vis[f(sx, sy)][f(bx, by)] = true; q.push([f(sx, sy), f(bx, by), d + 1]); } else if (!vis[f(sx, sy)][f(bi, bj)]) { vis[f(sx, sy)][f(bi, bj)] = true; q.unshift([f(sx, sy), f(bi, bj), d]); } } } return -1; } /* 以下是双向列队模板类 */ class CircularDeque<T> { prev: CircularDeque<T> | null; next: CircularDeque<T> | null; begin: number; end: number; empty: boolean; data: T[]; constructor(N: number) { this.prev = this.next = null; this.begin = this.end = 0; this.empty = true; this.data = Array(N); } isFull(): boolean { return this.end === this.begin && !this.empty; } isEmpty(): boolean { return this.empty; } push(val: T): boolean { if (this.isFull()) return false; this.empty = false; this.data[this.end] = val; this.end = (this.end + 1) % this.data.length; return true; } front(): T | undefined { return this.isEmpty() ? undefined : this.data[this.begin]; } back(): T | undefined { return this.isEmpty() ? undefined : this.data[this.end - 1]; } pop(): T | undefined { if (this.isEmpty()) return undefined; const value = this.data[this.end - 1]; this.end = (this.end - 1) % this.data.length; if (this.end < 0) this.end += this.data.length; if (this.end === this.begin) this.empty = true; return value; } unshift(val: T): boolean { if (this.isFull()) return false; this.empty = false; this.begin = (this.begin - 1) % this.data.length; if (this.begin < 0) this.begin += this.data.length; this.data[this.begin] = val; return true; } shift(): T | undefined { if (this.isEmpty()) return undefined; const value = this.data[this.begin]; this.begin = (this.begin + 1) % this.data.length; if (this.end === this.begin) this.empty = true; return value; } *values(): Generator<T, void, undefined> { if (this.isEmpty()) return undefined; let i = this.begin; do { yield this.data[i]; i = (i + 1) % this.data.length; } while (i !== this.end); } } class Deque<T> { head: CircularDeque<T>; tail: CircularDeque<T>; _size: number; constructor(collection: T[] = []) { this.head = new CircularDeque<T>(128); this.tail = new CircularDeque<T>(128); this.tail.empty = this.head.empty = false; this.tail.prev = this.head; this.head.next = this.tail; this._size = 0; for (const item of collection) this.push(item); } size(): number { return this._size; } push(val: T): void { let last = this.tail.prev!; if (last.isFull()) { const inserted = new CircularDeque<T>(128); this.tail.prev = inserted; inserted.next = this.tail; last.next = inserted; inserted.prev = last; last = inserted; } last.push(val); this._size++; } back(): T | undefined { if (this._size === 0) return; return this.tail.prev!.back(); } pop(): T | undefined { if (this.head.next === this.tail) return undefined; const last = this.tail.prev!; const value = last.pop(); if (last.isEmpty()) { this.tail.prev = last.prev; last.prev!.next = this.tail; } this._size--; return value; } unshift(val: T): void { let first = this.head.next!; if (first.isFull()) { const inserted = new CircularDeque<T>(128); this.head.next = inserted; inserted.prev = this.head; inserted.next = first; first.prev = inserted; first = inserted; } first.unshift(val); this._size++; } shift(): T | undefined { if (this.head.next === this.tail) return undefined; const first = this.head.next!; const value = first.shift(); if (first.isEmpty()) { this.head.next = first.next; first.next!.prev = this.head; } this._size--; return value; } front(): T | undefined { if (this._size === 0) return undefined; return this.head.next!.front(); } *values(): Generator<T, void, undefined> { let node = this.head.next!; while (node !== this.tail) { for (const value of node.values()) yield value; node = node.next!; } } }