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

All Problems

All Solutions