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

Java

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

All Problems

All Solutions