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—impossible! In this LeetCode problem, you’re tasked with figuring out the minimum number of moves required to push a box to a designated target location on a grid. Sounds simple, right? Well, let’s just say it’s a bit more complicated than convincing your cat to move.

Imagine you’re in a warehouse, and you have a box that needs to be pushed to a specific spot. But wait! There are walls, and you can’t just shove the box wherever you want. You have to navigate around obstacles, and your player character (that’s you!) has to be able to reach the box from behind to push it. It’s like a game of chess, but with a box and a player who’s not very good at strategy.

Navigation Links

Code Solution


class Solution {
 public:
  int minPushBox(vector>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    vector box;
    vector player;
    vector target;

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

    queue> q{
        {{box[0], box[1], player[0], player[1]}}};
    vector>>> seen(
        m, vector>>(
               n, vector>(m, vector(n))));
    seen[box[0]][box[1]][player[0]][player[1]] = true;

    for (int step = 0; !q.empty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [boxX, boxY, playerX, playerY] = q.front();
        q.pop();
        if (boxX == target[0] && boxY == target[1])
          return step;
        for (int k = 0; k < 4; ++k) {
          const int nextBoxX = boxX + dirs[k % 4][0];
          const int nextBoxY = boxY + dirs[k % 4][1];
          if (isInvalid(grid, nextBoxX, nextBoxY))
            continue;
          if (seen[nextBoxX][nextBoxY][boxX][boxY])
            continue;
          const int fromX = boxX + dirs[(k + 2) % 4][0];
          const 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.emplace(nextBoxX, nextBoxY, boxX, boxY);
          }
        }
      }

    return -1;
  }

 private:
  static constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

  bool canGoTo(const vector>& grid, int playerX, int playerY,
               int fromX, int fromY, int boxX, int boxY) {
    queue> q{{{playerX, playerY}}};
    vector> seen(grid.size(), vector(grid[0].size()));
    seen[playerX][playerY] = true;

    while (!q.empty()) {
      const auto [i, j] = q.front();
      q.pop();
      if (i == fromX && j == fromY)
        return true;
      for (const auto& [dx, dy] : dirs) {
        const int x = i + dx;
        const int y = j + dy;
        if (isInvalid(grid, x, y))
          continue;
        if (seen[x][y])
          continue;
        if (x == boxX && y == boxY)
          continue;
        q.emplace(x, y);
        seen[x][y] = true;
      }
    }

    return false;
  }

  bool isInvalid(const vector>& grid, int playerX, int playerY) {
    return playerX < 0 || playerX == grid.size() || playerY < 0 ||
           playerY == grid[0].size() || grid[playerX][playerY] == '#';
  }
};

Approach Explanation

The code uses a breadth-first search (BFS) approach to explore all possible moves to push the box to the target location. It maintains a queue to track the current state of the box and player positions. The algorithm checks all four possible directions to push the box and ensures that the player can reach the position behind the box to push it. If the box reaches the target, the function returns the number of moves taken.

Time and Space Complexity

Time Complexity: O(m * n * m * n), where m is the number of rows and n is the number of columns in the grid. This is due to the BFS exploring all possible states of the box and player.
Space Complexity: O(m * n * m * n) for the seen array that tracks visited states.

Real-World Example

Think of this problem like trying to move a heavy piece of furniture in your living room. You can’t just shove it wherever you want; you have to navigate around other furniture, walls, and maybe even a pet that’s decided to lay down in your path. You need to find the best way to push it to the desired spot without getting stuck or blocked.