Minimum Moves to Move a Box to Their Target Location

Ah, the classic dilemma of moving a box to its target location! It’s like trying to get your cat to move from the sunny spot on the floor to its bed. You know it can do it, but it just stares at you like you’ve asked it to solve a Rubik’s Cube. In this problem, you’re tasked with moving a box (let’s call it Bob) to a target location on a grid while avoiding obstacles (like that pesky couch that always seems to be in the way).

Imagine you’re in a warehouse, and you need to push a box to a specific spot. But wait! You can’t just shove it around like a toddler with a toy. You have to navigate through a maze of walls and ensure that you can actually reach the box to push it. Sounds fun, right?

Code Solution


class Solution {
  public int minPushBox(char[][] grid) {
    record T(int boxX, int boxY, int playerX, int playerY) {}
    final int m = grid.length;
    final int n = grid[0].length;
    int[] box = {-1, -1};
    int[] player = {-1, -1};
    int[] target = {-1, -1};

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i][j] == 'B')
          box = new int[] {i, j};
        else if (grid[i][j] == 'S')
          player = new int[] {i, j};
        else if (grid[i][j] == 'T')
          target = new int[] {i, j};

    Queue q = new ArrayDeque<>(List.of(new T(box[0], box[1], player[0], player[1])));
    boolean[][][][] seen = new boolean[m][n][m][n];
    seen[box[0]][box[1]][player[0]][player[1]] = true;

    for (int step = 0; !q.isEmpty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        final int boxX = q.peek().boxX;
        final int boxY = q.peek().boxY;
        final int playerX = q.peek().playerX;
        final int playerY = q.poll().playerY;
        if (boxX == target[0] && boxY == target[1])
          return step;
        for (int k = 0; k < 4; ++k) {
          final int nextBoxX = boxX + dirs[k][0];
          final int nextBoxY = boxY + dirs[k][1];
          if (isInvalid(grid, nextBoxX, nextBoxY))
            continue;
          if (seen[nextBoxX][nextBoxY][boxX][boxY])
            continue;
          final int fromX = boxX + dirs[(k + 2) % 4][0];
          final int fromY = boxY + dirs[(k + 2) % 4][1];
          if (isInvalid(grid, fromX, fromY))
            continue;
          if (canGoTo(grid, playerX, playerY, fromX, fromY, boxX, boxY)) {
            seen[nextBoxX][nextBoxY][boxX][boxY] = true;
            q.offer(new T(nextBoxX, nextBoxY, boxX, boxY));
          }
        }
      }

    return -1;
  }

  private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

  private boolean canGoTo(char[][] grid, int playerX, int playerY, int fromX, int fromY, int boxX,
                          int boxY) {
    Queue> q = new ArrayDeque<>(List.of(new Pair<>(playerX, playerY)));
    boolean[][] seen = new boolean[grid.length][grid[0].length];
    seen[playerX][playerY] = true;

    while (!q.isEmpty()) {
      final int i = q.peek().getKey();
      final int j = q.poll().getValue();
      if (i == fromX && j == fromY)
        return true;
      for (int[] dir : dirs) {
        final int x = i + dir[0];
        final int y = j + dir[1];
        if (isInvalid(grid, x, y))
          continue;
        if (seen[x][y])
          continue;
        if (x == boxX && y == boxY)
          continue;
        q.offer(new Pair<>(x, y));
        seen[x][y] = true;
      }
    }

    return false;
  }

  private boolean isInvalid(char[][] grid, int playerX, int playerY) {
    return playerX < 0 || playerX == grid.length || playerY < 0 || playerY == grid[0].length ||
        grid[playerX][playerY] == '#';
  }
}

Approach Explanation

The code uses a breadth-first search (BFS) approach to explore all possible moves to push the box to its target location. It maintains a queue to track the current state of the box and the player, and a 4D boolean array to keep track of visited states. The algorithm checks all four possible directions to push the box and verifies if the player can reach the position needed to push the box. If the box reaches the target, the function returns the number of moves taken.

Time and Space Complexity

Complexity Type Complexity
Time Complexity O(m * n * m * n)
Space Complexity O(m * n * m * n)

Real-World Example

Imagine you’re at a grocery store, and you need to push a cart full of groceries to the checkout. However, the aisles are crowded, and you can’t just bulldoze your way through. You have to navigate around other shoppers and displays, making sure you can actually reach the checkout without getting stuck. This is similar to the box-pushing problem, where you need to find the optimal path to move the box (or cart) to its target location while avoiding obstacles.

Similar Problems