Question

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 1: Double-ended Queue + BFS

We consider the player's position and the box's position as a state, i.e., $(s_i, s_j, b_i, b_j)$, where $(s_i, s_j)$ is the player's position, and $(b_i, b_j)$ is the box's position. In the code implementation, we define a function $f(i, j)$, which maps the two-dimensional coordinates $(i, j)$ to a one-dimensional state number, i.e., $f(i, j) = i \times n + j$, where $n$ is the number of columns in the grid. So the player and the box's state is $(f(s_i, s_j), f(b_i, b_j))$.

First, we traverse the grid to find the initial positions of the player and the box, denoted as $(s_i, s_j)$ and $(b_i, b_j)$.

Then, we define a double-ended queue $q$, where each element is a triplet $(f(s_i, s_j), f(b_i, b_j), d)$, indicating that the player is at $(s_i, s_j)$, the box is at $(b_i, b_j)$, and $d$ pushes have been made. Initially, we add $(f(s_i, s_j), f(b_i, b_j), 0)$ to the queue $q$.

Additionally, we use a two-dimensional array $vis$ to record whether each state has been visited. Initially, $vis[f(s_i, s_j), f(b_i, b_j)]$ is marked as visited.

Next, we start the breadth-first search.

In each step of the search, we take out the queue head element $(f(s_i, s_j), f(b_i, b_j), d)$, and check whether $grid[b_i][b_j] = 'T'$ is satisfied. If it is, it means the box has been pushed to the target position, and now $d$ can be returned as the answer.

Otherwise, we enumerate the player's next move direction. The player's new position is denoted as $(s_x, s_y)$. If $(s_x, s_y)$ is a valid position, we judge whether $(s_x, s_y)$ is the same as the box's position $(b_i, b_j)$:

• If they are the same, it means the player has reached the box's position and pushed the box forward by one step. The box's new position is $(b_x, b_y)$. If $(b_x, b_y)$ is a valid position, and the state $(f(s_x, s_y), f(b_x, b_y))$ has not been visited, then we add $(f(s_x, s_y), f(b_x, b_y), d + 1)$ to the end of the queue $q$, and mark $vis[f(s_x, s_y), f(b_x, b_y)]$ as visited.
• If they are different, it means the player has not pushed the box. Then we only need to judge whether the state $(f(s_x, s_y), f(b_i, b_j))$ has been visited. If it has not been visited, then we add $(f(s_x, s_y), f(b_i, b_j), d)$ to the head of the queue $q$, and mark $vis[f(s_x, s_y), f(b_i, b_j)]$ as visited.

We continue the breadth-first search until the queue is empty.

Note, if the box is pushed, the push count $d$ needs to be incremented by $1$, and the new state is added to the end of the queue $q$. If the box is not pushed, the push count $d$ remains unchanged, and the new state is added to the head of the queue $q$.

Finally, if no valid push scheme is found, then return $-1$.

The time complexity is $O(m^2 \times n^2)$, and the space complexity is $O(m^2 \times n^2)$. Where $m$ and $n$ are the number of rows and columns in the grid, respectively.

class Solution:
  def minPushBox(self, grid: List[List[str]]) -> int:
    def f(i: int, j: int) -> int:
      return i * n + j

    def check(i: int, j: int) -> bool:
      return 0 <= i < m and 0 <= j < n and grid[i][j] != "#"

    for i, row in enumerate(grid):
      for j, c in enumerate(row):
        if c == "S":
          si, sj = i, j
        elif c == "B":
          bi, bj = i, j
    m, n = len(grid), len(grid[0])
    dirs = (-1, 0, 1, 0, -1)
    q = deque([(f(si, sj), f(bi, bj), 0)])
    vis = [[False] * (m * n) for _ in range(m * n)]
    vis[f(si, sj)][f(bi, bj)] = True
    while q:
      s, b, d = q.popleft()
      bi, bj = b // n, b % n
      if grid[bi][bj] == "T":
        return d
      si, sj = s // n, s % n
      for a, b in pairwise(dirs):
        sx, sy = si + a, sj + b
        if not check(sx, sy):
          continue
        if sx == bi and sy == bj:
          bx, by = bi + a, bj + b
          if not check(bx, by) or vis[f(sx, sy)][f(bx, by)]:
            continue
          vis[f(sx, sy)][f(bx, by)] = True
          q.append((f(sx, sy), f(bx, by), d + 1))
        elif not vis[f(sx, sy)][f(bi, bj)]:
          vis[f(sx, sy)][f(bi, bj)] = True
          q.appendleft((f(sx, sy), f(bi, bj), d))
    return -1

class Solution {
  private int m;
  private int n;
  private char[][] grid;

  public int minPushBox(char[][] grid) {
    m = grid.length;
    n = grid[0].length;
    this.grid = grid;
    int si = 0, sj = 0, bi = 0, bj = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 'S') {
          si = i;
          sj = j;
        } else if (grid[i][j] == 'B') {
          bi = i;
          bj = j;
        }
      }
    }
    int[] dirs = {-1, 0, 1, 0, -1};
    Deque<int[]> q = new ArrayDeque<>();
    boolean[][] vis = new boolean[m * n][m * n];
    q.offer(new int[] {f(si, sj), f(bi, bj), 0});
    vis[f(si, sj)][f(bi, bj)] = true;
    while (!q.isEmpty()) {
      var p = q.poll();
      int d = p[2];
      bi = p[1] / n;
      bj = p[1] % n;
      if (grid[bi][bj] == 'T') {
        return d;
      }
      si = p[0] / n;
      sj = p[0] % n;
      for (int k = 0; k < 4; ++k) {
        int sx = si + dirs[k], sy = sj + dirs[k + 1];
        if (!check(sx, sy)) {
          continue;
        }
        if (sx == bi && sy == bj) {
          int bx = bi + dirs[k], by = bj + dirs[k + 1];
          if (!check(bx, by) || vis[f(sx, sy)][f(bx, by)]) {
            continue;
          }
          vis[f(sx, sy)][f(bx, by)] = true;
          q.offer(new int[] {f(sx, sy), f(bx, by), d + 1});
        } else if (!vis[f(sx, sy)][f(bi, bj)]) {
          vis[f(sx, sy)][f(bi, bj)] = true;
          q.offerFirst(new int[] {f(sx, sy), f(bi, bj), d});
        }
      }
    }
    return -1;
  }

  private int f(int i, int j) {
    return i * n + j;
  }

  private boolean check(int i, int j) {
    return i >= 0 && i < m && j >= 0 && j < n && grid[i][j] != '#';
  }
}

class Solution {
public:
  int minPushBox(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size();
    int si, sj, bi, bj;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 'S') {
          si = i, sj = j;
        } else if (grid[i][j] == 'B') {
          bi = i, bj = j;
        }
      }
    }
    auto f = [&](int i, int j) {
      return i * n + j;
    };
    auto check = [&](int i, int j) {
      return i >= 0 && i < m && j >= 0 && j < n && grid[i][j] != '#';
    };
    int dirs[5] = {-1, 0, 1, 0, -1};
    deque<tuple<int, int, int>> q;
    q.emplace_back(f(si, sj), f(bi, bj), 0);
    bool vis[m * n][m * n];
    memset(vis, false, sizeof(vis));
    vis[f(si, sj)][f(bi, bj)] = true;
    while (!q.empty()) {
      auto [s, b, d] = q.front();
      q.pop_front();
      si = s / n, sj = s % n;
      bi = b / n, bj = b % n;
      if (grid[bi][bj] == 'T') {
        return d;
      }
      for (int k = 0; k < 4; ++k) {
        int sx = si + dirs[k], sy = sj + dirs[k + 1];
        if (!check(sx, sy)) {
          continue;
        }
        if (sx == bi && sy == bj) {
          int bx = bi + dirs[k], by = bj + dirs[k + 1];
          if (!check(bx, by) || vis[f(sx, sy)][f(bx, by)]) {
            continue;
          }
          vis[f(sx, sy)][f(bx, by)] = true;
          q.emplace_back(f(sx, sy), f(bx, by), d + 1);
        } else if (!vis[f(sx, sy)][f(bi, bj)]) {
          vis[f(sx, sy)][f(bi, bj)] = true;
          q.emplace_front(f(sx, sy), f(bi, bj), d);
        }
      }
    }
    return -1;
  }
};

func minPushBox(grid [][]byte) int {
  m, n := len(grid), len(grid[0])
  var si, sj, bi, bj int
  for i, row := range grid {
    for j, c := range row {
      if c == 'S' {
        si, sj = i, j
      } else if c == 'B' {
        bi, bj = i, j
      }
    }
  }
  f := func(i, j int) int {
    return i*n + j
  }
  check := func(i, j int) bool {
    return i >= 0 && i < m && j >= 0 && j < n && grid[i][j] != '#'
  }
  q := [][]int{[]int{f(si, sj), f(bi, bj), 0}}
  vis := make([][]bool, m*n)
  for i := range vis {
    vis[i] = make([]bool, m*n)
  }
  vis[f(si, sj)][f(bi, bj)] = true
  dirs := [5]int{-1, 0, 1, 0, -1}
  for len(q) > 0 {
    p := q[0]
    q = q[1:]
    si, sj, bi, bj = p[0]/n, p[0]%n, p[1]/n, p[1]%n
    d := p[2]
    if grid[bi][bj] == 'T' {
      return d
    }
    for k := 0; k < 4; k++ {
      sx, sy := si+dirs[k], sj+dirs[k+1]
      if !check(sx, sy) {
        continue
      }
      if sx == bi && sy == bj {
        bx, by := bi+dirs[k], bj+dirs[k+1]
        if !check(bx, by) || vis[f(sx, sy)][f(bx, by)] {
          continue
        }
        vis[f(sx, sy)][f(bx, by)] = true
        q = append(q, []int{f(sx, sy), f(bx, by), d + 1})
      } else if !vis[f(sx, sy)][f(bi, bj)] {
        vis[f(sx, sy)][f(bi, bj)] = true
        q = append([][]int{[]int{f(sx, sy), f(bi, bj), d}}, q...)
      }
    }
  }
  return -1
}

function minPushBox(grid: string[][]): number {
  const [m, n] = [grid.length, grid[0].length];
  let [si, sj, bi, bj] = [0, 0, 0, 0];
  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
      if (grid[i][j] === 'S') {
        [si, sj] = [i, j];
      } else if (grid[i][j] === 'B') {
        [bi, bj] = [i, j];
      }
    }
  }
  const f = (i: number, j: number): number => i * n + j;
  const check = (i: number, j: number): boolean =>
    i >= 0 && i < m && j >= 0 && j < n && grid[i][j] !== '#';

  const q: Deque<[number, number, number]> = new Deque();
  const vis: boolean[][] = new Array(m * n).fill(0).map(() => new Array(m * n).fill(false));
  q.push([f(si, sj), f(bi, bj), 0]);
  vis[f(si, sj)][f(bi, bj)] = true;
  const dirs: number[] = [-1, 0, 1, 0, -1];
  while (q.size() > 0) {
    const [s, b, d] = q.shift()!;
    const [si, sj] = [Math.floor(s / n), s % n];
    const [bi, bj] = [Math.floor(b / n), b % n];
    if (grid[bi][bj] === 'T') {
      return d;
    }
    for (let k = 0; k < 4; ++k) {
      const [sx, sy] = [si + dirs[k], sj + dirs[k + 1]];
      if (!check(sx, sy)) {
        continue;
      }
      if (sx === bi && sy === bj) {
        const [bx, by] = [bi + dirs[k], bj + dirs[k + 1]];
        if (!check(bx, by) || vis[f(sx, sy)][f(bx, by)]) {
          continue;
        }
        vis[f(sx, sy)][f(bx, by)] = true;
        q.push([f(sx, sy), f(bx, by), d + 1]);
      } else if (!vis[f(sx, sy)][f(bi, bj)]) {
        vis[f(sx, sy)][f(bi, bj)] = true;
        q.unshift([f(sx, sy), f(bi, bj), d]);
      }
    }
  }
  return -1;
}

/* 以下是双向列队模板类 */
class CircularDeque<T> {
  prev: CircularDeque<T> | null;
  next: CircularDeque<T> | null;
  begin: number;
  end: number;
  empty: boolean;
  data: T[];
  constructor(N: number) {
    this.prev = this.next = null;
    this.begin = this.end = 0;
    this.empty = true;
    this.data = Array(N);
  }

  isFull(): boolean {
    return this.end === this.begin && !this.empty;
  }

  isEmpty(): boolean {
    return this.empty;
  }

  push(val: T): boolean {
    if (this.isFull()) return false;
    this.empty = false;
    this.data[this.end] = val;
    this.end = (this.end + 1) % this.data.length;
    return true;
  }

  front(): T | undefined {
    return this.isEmpty() ? undefined : this.data[this.begin];
  }

  back(): T | undefined {
    return this.isEmpty() ? undefined : this.data[this.end - 1];
  }

  pop(): T | undefined {
    if (this.isEmpty()) return undefined;
    const value = this.data[this.end - 1];
    this.end = (this.end - 1) % this.data.length;
    if (this.end < 0) this.end += this.data.length;
    if (this.end === this.begin) this.empty = true;
    return value;
  }

  unshift(val: T): boolean {
    if (this.isFull()) return false;
    this.empty = false;
    this.begin = (this.begin - 1) % this.data.length;
    if (this.begin < 0) this.begin += this.data.length;
    this.data[this.begin] = val;
    return true;
  }

  shift(): T | undefined {
    if (this.isEmpty()) return undefined;
    const value = this.data[this.begin];
    this.begin = (this.begin + 1) % this.data.length;
    if (this.end === this.begin) this.empty = true;
    return value;
  }

  *values(): Generator<T, void, undefined> {
    if (this.isEmpty()) return undefined;
    let i = this.begin;
    do {
      yield this.data[i];
      i = (i + 1) % this.data.length;
    } while (i !== this.end);
  }
}

class Deque<T> {
  head: CircularDeque<T>;
  tail: CircularDeque<T>;
  _size: number;
  constructor(collection: T[] = []) {
    this.head = new CircularDeque<T>(128);
    this.tail = new CircularDeque<T>(128);
    this.tail.empty = this.head.empty = false;
    this.tail.prev = this.head;
    this.head.next = this.tail;
    this._size = 0;
    for (const item of collection) this.push(item);
  }

  size(): number {
    return this._size;
  }

  push(val: T): void {
    let last = this.tail.prev!;
    if (last.isFull()) {
      const inserted = new CircularDeque<T>(128);

      this.tail.prev = inserted;
      inserted.next = this.tail;

      last.next = inserted;
      inserted.prev = last;

      last = inserted;
    }
    last.push(val);
    this._size++;
  }

  back(): T | undefined {
    if (this._size === 0) return;
    return this.tail.prev!.back();
  }

  pop(): T | undefined {
    if (this.head.next === this.tail) return undefined;
    const last = this.tail.prev!;
    const value = last.pop();
    if (last.isEmpty()) {
      this.tail.prev = last.prev;
      last.prev!.next = this.tail;
    }
    this._size--;
    return value;
  }

  unshift(val: T): void {
    let first = this.head.next!;
    if (first.isFull()) {
      const inserted = new CircularDeque<T>(128);

      this.head.next = inserted;
      inserted.prev = this.head;

      inserted.next = first;
      first.prev = inserted;

      first = inserted;
    }
    first.unshift(val);
    this._size++;
  }

  shift(): T | undefined {
    if (this.head.next === this.tail) return undefined;
    const first = this.head.next!;
    const value = first.shift();
    if (first.isEmpty()) {
      this.head.next = first.next;
      first.next!.prev = this.head;
    }
    this._size--;
    return value;
  }

  front(): T | undefined {
    if (this._size === 0) return undefined;
    return this.head.next!.front();
  }

  *values(): Generator<T, void, undefined> {
    let node = this.head.next!;
    while (node !== this.tail) {
      for (const value of node.values()) yield value;
      node = node.next!;
    }
  }
}