1263. Minimum Moves to Move a Box to Their Target Location

Description

A 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 an m x n grid of characters grid where each element is a wall, floor, or box.

Your task is to move the box 'B' to the target position 'T' under the following rules:

• The character 'S' represents the player. The player can move up, down, left, right in grid if it is a floor (empty cell).
• The character '.' represents the floor which means a free cell to walk.
• The character'#'represents the wall which means an 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.

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 20
• grid contains only characters '.', '#', 'S', 'T', or 'B'.
• There is only one character 'S', 'B', and 'T' in the grid.

 

Solutions

Solution: Breadth-First Search

• Time complexity: O(（mn)³)
• Space complexity: O(（mn)²)

 

JavaScript

/**
 * @param {character[][]} grid
 * @return {number}
 */
const minPushBox = function (grid) {
  const OBSTACLE = '#';
  const m = grid.length;
  const n = grid[0].length;
  const location = { player: null, box: null };

  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      const value = grid[row][col];

      if (value === 'S') location.player = { row, col };
      if (value === 'B') location.box = { row, col };
    }
  }
  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  const visited = new Set();
  let queue = [location];
  let result = 0;

  const isOutOfBounds = (row, col) => row >= m || col >= n || row < 0 || col < 0;
  const getVisitedKey = (box, player) => `${box.row},${box.col},${player.row},${player.col}`;

  const playerCanMoveTo = (start, target, box) => {
    if (start.row === target.row && start.col === target.col) return true;
    const memo = Array.from({ length: m * n }, () => false);
    let queue = [start];

    memo[start.row * n + start.col] = true;

    while (queue.length) {
      const nextQueue = [];

      for (const { row, col } of queue) {
        for (const [moveRow, moveCol] of directions) {
          const nextRow = row + moveRow;
          const nextCol = col + moveCol;
          const key = nextRow * n + nextCol;

          if (nextRow === target.row && nextCol === target.col) return true;
          if (isOutOfBounds(nextRow, nextCol) || memo[key]) continue;
          if (nextRow === box.row && nextCol === box.col) continue;
          if (grid[nextRow][nextCol] === OBSTACLE) continue;

          nextQueue.push({ row: nextRow, col: nextCol });
          memo[key] = true;
        }
      }
      queue = nextQueue;
    }
    return false;
  };

  visited.add(getVisitedKey(location.box, location.player));

  while (queue.length) {
    const nextQueue = [];

    result += 1;

    for (const { player, box } of queue) {
      for (const [moveRow, moveCol] of directions) {
        const nextRow = box.row + moveRow;
        const nextCol = box.col + moveCol;

        if (isOutOfBounds(nextRow, nextCol)) continue;
        const nextBox = { row: nextRow, col: nextCol };
        const boxCell = grid[nextRow][nextCol];

        if (boxCell === OBSTACLE) continue;
        const pushRow = box.row + moveRow * -1;
        const pushCol = box.col + moveCol * -1;

        if (isOutOfBounds(pushRow, pushCol)) continue;
        if (grid[pushRow][pushCol] === OBSTACLE) continue;
        const pushPosition = { row: pushRow, col: pushCol };
        const key = getVisitedKey(nextBox, pushPosition);

        if (visited.has(key)) continue;
        if (!playerCanMoveTo(player, pushPosition, box)) continue;
        if (boxCell === 'T') return result;

        nextQueue.push({ player: box, box: nextBox });
        visited.add(key);
      }
    }
    queue = nextQueue;
  }
  return -1;
};