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 thegridif 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.lengthn == grid[i].length1 <= m <= 201 <= n <= 20gridcontains 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;
}
};
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; } } -
// 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; } }; -
print("Todo!")