📦 推箱子

📝 题目描述

「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。

游戏地图用大小为m x n的网格grid表示，其中每个元素可以是墙、地板或者是箱子。

现在你将作为玩家参与游戏，按规则将箱子'B'移动到目标位置'T'：

玩家用字符'S'表示，只要他在地板上，就可以在网格中向上、下、左、右四个方向移动。
地板用字符'.'表示，意味着可以自由行走。
墙用字符'#'表示，意味着障碍物，不能通行。
箱子仅有一个，用字符'B'表示。相应地，网格上有一个目标位置'T'。
玩家需要站在箱子旁边，然后沿着箱子的方向进行移动，此时箱子会被移动到相邻的地板单元格。记作一次「推动」。
玩家无法越过箱子

返回将箱子推到目标位置的最小推动次数，如果无法做到，请返回-1。

📋 代码模板

javatypescript

java

class Solution {
    public int minPushBox(char[][] grid) {

    }
}

typescript

function minPushBox(grid: string[][]): number {
    
}

💡 提示

$m == g r i d . l e n g t h$
$n == g r i d [i] . l e n g t h$
$1 \leq m 20$
$1 \leq n \leq 20$
$g r i d$ 仅包含字符'.'、'#'、'S'、'T'以及'B'
$g r i d$ 中 'S'、'B'和'T'各只能出现一个

🚀 示例

示例一

输入grid为[['#','#','#','#','#','#'],['#','T','#','#','#','#'],['#','.','.','B','.','#'],['#','.','#','#','.','#'],['#','.','.','.','S','#'],['#','#','#','#','#','#']]，输出为3。首先我们可以通过向上2步移动至单元格(2,4)往左推动箱子2次，其次通过向右2步->向下2步原路返回至起点，最后通过向左3步->向上1步移动至单元格(3,1)往上推动箱子1次后到达目标位置。具体步骤如下图所示。

示例二

输入grid为[['#','#','#','#','#','#'],['#','T','#','#','#','#'],['#','.','.','B','.','#'],['#','#','#','#','.','#'],['#','.','.','.','S','#'],['#','#','#','#','#','#']]，输出为-1。在该网格中，我们只能将箱子推动至单元格(2,1)。

示例三

输入grid为[['#','#','#','#','#','#'],['#','T','.','.','#','#'],['#','.','#','B','.','#'],['#','.','.','.','.','#'],['#','.','.','.','S','#'],['#','#','#','#','#','#']]，输出为5。首先我们可以通过向左3步->向上3步->向右2步移动至单元格(1,3)往下推动箱子1次，其次通过向右1步->向下1步移动至单元格(3,4)往左推动箱子2次，最后通过向下1步->向左1步移动至单元格(4,1)往上推动箱子2次后到达目标位置。具体步骤如下图所示。

🖊️ 题解

本题的难点在于玩家需要将箱子推到目标点位，而不是简单地移动到目标点位。箱子的移动依赖于玩家的移动，当玩家移动到箱子所在的点位时，就可以将箱子往同样的方向移动一格，如果箱子移动到了合法位置，那么我们就可以将这个过程记为一次「推动」，否则玩家移动无效。

玩家的移动可以通过BFS算法进行模拟。但从示例一中可以看出，如果箱子移动了，玩家是可以通过走”回头路“（已访问过的路）来再次推动箱子的。为此，我们可以把玩家的位置与箱子的位置一起看成一个状态，并使用一个 $v i s i t e d$ 数组来记录每个状态是否已被访问。如果一个状态已经被访问过，我们就可以跳过它以避免重复。假设玩家的位置为 $(s_{i}, s_{j})$ ，箱子的位置为 $(b_{i}, b_{j})$ ，我们可以通过定义一个函数 $f (i, j)$ 将玩家和箱子的位置共同记为一个二维状态 $(f (s_{i}, s_{j}), f (b_{i}, b_{j}))$ 。 $f$ 函数可以将一个二维坐标映射成一个一维的状态编号，具体实现为 $f （ i, j ） = i \times n + j$ ，这样一来，如果得到一个一维状态编号 $s t a t e$ ，那么它对应的横坐标为 $⌊ \frac{s t a t e}{n} ⌋$ ，纵坐标为 $s t a t e \mod n$ ，因为方程式中的 $j$ 永远小于 $n$ 。

除了要记录玩家和箱子的位置外，我们还需记录推动箱子的次数，每当玩家推动一次箱子，就把这个计数加 $1$ ，所以当前的整体状态可以用一个三元组 $(f (s_{i}, s_{j}), f (b_{i}, b_{j}), c n t)$ 来表示，其中 $c n t$ 表示当前推动次数。由于题目要求寻找最小推动次数，因此在进行BFS时，我们可以准备一个双端队列，并将推动箱子的状态放入队尾，而未推动箱子的状态则放在队首，且每次都取队首元素作搜索。在搜索时，如果当前状态对应的箱子位置已经到达了目标位置，应立即返回 $t r u e$ 。搜索结束后，此时说明玩家不能将箱子推至目标位置，应返回 $f a l s e$ 。

javatypescript

java

class Solution {
    private final static char PLAYER = 'S', WALL = '#', BOX = 'B', DEST = 'T';
    private final static int[][] DIRS = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int minPushBox(char[][] grid) {
        final int m = grid.length, n = grid[0].length;
        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] == PLAYER) {
                    si = i;
                    sj = j;
                    continue;
                }
                if (grid[i][j] == BOX) {
                    bi = i;
                    bj = j;
                }
            }
        }
        Deque<int[]> deque = new LinkedList<>();
        int playerState = f(si, sj, n), boxState = f(bi, bj, n);
        deque.offerFirst(new int[]{playerState, boxState, 0});
        boolean[][] visited = new boolean[m * n][m * n];
        visited[playerState][boxState] = true;
        while (!deque.isEmpty()) {
            int[] cell = deque.pollFirst();
            int oldSI = cell[0] / n, oldSJ = cell[0] % n;
            int oldBI = cell[1] / n, oldBJ = cell[1] % n;
            int cnt = cell[2];
            if (grid[oldBI][oldBJ] == DEST) {
                return cnt;
            }
            for (int d = 0; d < 4; d++) {
                int newSI = oldSI + DIRS[d][0], newSJ = oldSJ + DIRS[d][1];
                if (!isValid(grid, newSI, newSJ)) {
                    continue;
                }
                int newPlayerState = f(newSI, newSJ, n);
                if (oldBI == newSI && oldBJ == newSJ) {
                    int newBI = oldBI + DIRS[d][0], newBJ = oldBJ + DIRS[d][1];
                    int newBoxState = f(newBI, newBJ, n);
                    if (isValid(grid, newBI, newBJ) && !visited[newPlayerState][newBoxState]) {
                        deque.offerLast(new int[]{newPlayerState, newBoxState, cnt + 1});
                        visited[newPlayerState][newBoxState] = true;
                    }
                    continue;
                }
                if (!visited[newPlayerState][cell[1]]) {
                    visited[newPlayerState][cell[1]] = true;
                    deque.offerFirst(new int[]{newPlayerState, cell[1], cnt});
                }
            }
        }
        return -1;
    }

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

    private boolean isValid(char[][] grid, int i, int j) {
        return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] != WALL;
    }
}

typescript

interface Deque<T> {
    pushLast(val: T): void;

    pushFirst(val: T): void;

    popLast(): T | null;

    popFirst(): T | null;

    peekLast(): T | null;

    peekFirst(): T | null;

    size(): number;

    isEmpty(): boolean;
}

class LNode<T> {
    prev: LNode<T> | null = null;
    next: LNode<T> | null = null;
    val: T;

    constructor(val: T) {
        this.val = val;
    }
}

class LinkedListDeque<T> implements Deque<T> {
    private front: LNode<T> | null = null;
    private rear: LNode<T> | null = null;
    private queueSize: number;

    constructor() {
        this.queueSize = 0;
    }

    pushLast(val: T): void {
        const node = new LNode(val);
        if (this.isEmpty()) {
            this.front = this.rear = node;
        } else {
            this.rear!.next = node;
            node.prev = this.rear;
            this.rear = node;
        }
        this.queueSize++;
    }

    pushFirst(val: T): void {
        const node = new LNode(val);
        if (this.isEmpty()) {
            this.front = this.rear = node;
        } else {
            this.front!.prev = node;
            node.next = this.front;
            this.front = node;
        }
        this.queueSize++;
    }

    popLast(): T | null {
        if (this.isEmpty()) {
            return null;
        }
        const value: T = this.rear!.val;
        let temp: LNode<T> | null = this.rear!.prev;
        if (temp) {
            temp.next = null;
            this.rear!.prev = null;
        }
        this.rear = temp;
        this.queueSize--;
        return value;
    }

    popFirst(): T | null {
        if (this.isEmpty()) {
            return null;
        }
        const value: T = this.front!.val;
        let temp: LNode<T> | null = this.front!.next;
        if (temp) {
            temp.prev = null;
            this.front!.next = null;
        }
        this.front = temp;
        this.queueSize--;
        return value;
    }

    peekLast(): T | null {
        return this.isEmpty() ? null : this.rear!.val;
    }

    peekFirst(): T | null {
        return this.isEmpty() ? null : this.front!.val;
    }

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

    isEmpty(): boolean {
        return this.queueSize == 0;
    }
}

const PLAYER = "S", WALL = "#", BOX = "B", DEST = "T";
const DIRS: number[][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];

function minPushBox(grid: string[][]): number {
    const m = grid.length, n = grid[0].length;
    const f = (i: number, j: number): number => {
        return i * n + j;
    }
    const isValid = (i: number, j: number): boolean => {
        return i >= 0 && i < m && j >= 0 && j < n && grid[i][j] != WALL;
    }
    let si = 0, sj = 0, bi = 0, bj = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] == PLAYER) {
                si = i;
                sj = j;
                continue;
            }
            if (grid[i][j] == BOX) {
                bi = i;
                bj = j;
            }
        }
    }
    const deque: Deque<number[]> = new LinkedListDeque();
    const playerState = f(si, sj), boxState = f(bi, bj);
    deque.pushFirst([playerState, boxState, 0]);
    const visited: boolean[][] = Array.from({length: m * n},
        () => Array(m * n).fill(false));
    visited[playerState][boxState] = true;
    while (!deque.isEmpty()) {
        const cell: number[] = deque.popFirst()!;
        const oldSI = Math.floor(cell[0] / n), oldSJ = cell[0] % n;
        const oldBI = Math.floor(cell[1] / n), oldBJ = cell[1] % n;
        const cnt = cell[2];
        if (grid[oldBI][oldBJ] == DEST) {
            return cnt;
        }
        for (let d = 0; d < 4; d++) {
            const newSI = oldSI + DIRS[d][0], newSJ = oldSJ + DIRS[d][1];
            if (!isValid(newSI, newSJ)) {
                continue;
            }
            const newPlayerState = f(newSI, newSJ);
            if (newSI == oldBI && newSJ == oldBJ) {
                const newBI = oldBI + DIRS[d][0], newBJ = oldBJ + DIRS[d][1];
                const newBoxState = f(newBI, newBJ);
                if (isValid(newBI, newBJ) && !visited[newPlayerState][newBoxState]) {
                    visited[newPlayerState][newBoxState] = true;
                    deque.pushLast([newPlayerState, newBoxState, cnt + 1]);
                }
                continue;
            }
            if (!visited[newPlayerState][cell[1]]) {
                visited[newPlayerState][cell[1]] = true;
                deque.pushFirst([newPlayerState, cell[1], cnt]);
            }
        }
    }
    return -1;
}

💭 复杂度分析

基于DFS + 双端队列的解决方案的复杂度分析如下。

时间复杂度： $O (m^{2} n^{2})$ 。其中 $m$ 与 $n$ 分别为网格的行数和列数。
空间复杂度： $O (m^{2} n^{2})$ 。

📦 推箱子 ​

📝 题目描述 ​

📋 代码模板 ​

💡 提示 ​

🚀 示例 ​

示例一 ​

示例二 ​

示例三 ​

🖊️ 题解 ​

💭 复杂度分析 ​