1263. 推箱子

题目链接：1263. 推箱子

方法：双端队列 + BFS

解题思路

[Python3/Java/C++/Go/TypeScript] 一题一解：双端队列 BFS（清晰题解）

代码

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}; // 下一步走法(dirs[i], dirs[i + 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); // 推动箱子，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); // 没有推动箱子，d，处于本层，加入队首
                }
            }
        }
        return -1;
    }
};