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 the grid 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 the grid.
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 the grid.

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!;
        }
    }
}

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

1263. Minimum Moves to Move a Box to Their Target Location (Hard)

Solution 1. BFS + DP

All Problems

All Solutions

Welcome to Subscribe On Youtube

1263. Minimum Moves to Move a Box to Their Target Location (Hard)

Solution 1. BFS + DP

All Problems

All Solutions