Minimum Moves to Move a Box to Their Target Location
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.
Solution:
class Solution {
int[] bdx = new int[]{-1, 0, 0, 1};
int[] bdy = new int[]{0, -1, 1, 0};
int[] pdx = new int[]{1, 0, 0, -1};
int[] pdy = new int[]{0, 1, -1, 0};
public int minPushBox(char[][] grid) {
int m = grid.length, n = grid[0].length;
int tx = -1, ty = -1;
int px = -1, py = -1;
int bx = -1, by = -1;
for (int i = 0; i < m; i ++) {
for (int j = 0; j < n; j ++) {
if (grid[i][j] == 'T') {
tx = i;
ty = j;
}
if (grid[i][j] == 'S') {
px = i;
py = j;
}
if (grid[i][j] == 'B') {
bx = i;
by = j;
}
}
}
grid[px][py] = '.';
grid[tx][ty] = '.';
grid[bx][by] = '.';
List<Integer> start = Arrays.asList(bx, by, px, py, 0);
Integer[][][][] visited = new Integer[m][n][m][n];
PriorityQueue<List<Integer>> queue = new PriorityQueue<List<Integer>>((a, b) -> Integer.compare(a.get(4), b.get(4)));
visited[bx][by][px][py] = 0;
queue.offer(start);
while (!queue.isEmpty()) {
List<Integer> curr = queue.poll();
// System.out.println(curr);
int cbx = curr.get(0);
int cby = curr.get(1);
int cstep = curr.get(4);
if (cbx == tx && cby == ty) return cstep;
int cpx = curr.get(2);
int cpy = curr.get(3);
for (int k = 0; k < 4; k ++) {
int nbx = cbx + bdx[k];
int nby = cby + bdy[k];
int tpx = cbx + pdx[k];
int tpy = cby + pdy[k];
int npx = nbx + pdx[k];
int npy = nby + pdy[k];
int nstep = cstep + 1;
if (
(nbx >= 0 && nbx < m && nby >= 0 && nby < n && grid[nbx][nby] != '#') &&
(npx >= 0 && npx < m && npy >= 0 && npy < n && grid[npx][npy] != '#')
) {
List<Integer> next = Arrays.asList(nbx, nby, npx, npy, nstep);
if (visited[nbx][nby][npx][npy] == null || visited[nbx][nby][npx][npy] > nstep) {
char[][] gridCopy = new char[m][n];
for (int p = 0; p < m; p ++) {
gridCopy[p] = grid[p].clone();
}
gridCopy[cbx][cby] = '#';
// gridCopy[cpx][cpy] = 'P';
// gridCopy[tpx][tpy] = 'T';
boolean[][] visited2 = new boolean[m][n];
visited2[cpx][cpy] = true;
// for (char[] arr : gridCopy) {
// System.out.println(Arrays.toString(arr));
// }
// System.out.println("-------------------------------");
if (canReach(gridCopy, cpx, cpy, tpx, tpy, visited2)) {
visited[nbx][nby][npx][npy] = nstep;
queue.offer(next);
}
}
}
}
}
return -1;
}
private boolean canReach(char[][] grid, int cpx, int cpy, int tpx, int tpy, boolean[][] visited) {
int m = grid.length, n = grid[0].length;
if (cpx == tpx && cpy == tpy) return true;
for (int k = 0; k < 4; k ++) {
int npx = cpx + bdx[k];
int npy = cpy + bdy[k];
if (npx >= 0 && npx < m && npy >= 0 && npy < n && grid[npx][npy] == '.' && !visited[npx][npy]) {
visited[npx][npy] = true;
if (canReach(grid, npx, npy, tpx, tpy, visited)) {
return true;
}
}
}
return false;
}
}