题目链接：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;
}
};