返回将箱子推到目标位置的最小推动次数，如果无法做到，请返回 -1。
一. 01广度优先搜索 + 双端队列
将人与箱子位置状态看做一个节点，在该题中人移动无需代价，即节点转移无需代价，所以边的权值为0
推动箱子移动耗费代价，推动箱子的边权值为1
最终目标是箱子达到目标位置，人的位置可能有多个，问题转化为求取对应状态图，到任意满足条件节点的最小代价
将坐标转化为一维，得到状态dp[i][j]，i表示人的位置，j表示箱子位置，用来防止重复遍历，以及进行剪枝
接下来进行状态转移
class Solution {
public:
int minPushBox(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
int sx, sy, bx, by; // 玩家、箱子的初始位置
for (int x = 0; x < m; x++) {//读取初始二维位置
for (int y = 0; y < n; y++) {
if (grid[x][y] == 'S') {
sx = x;
sy = y;
} else if (grid[x][y] == 'B') {
bx = x;
by = y;
}
}
}
auto ok = [&](int x, int y) -> bool { // 判断当前位置是否合法
return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != '#';
};
vector<int> d = {0, -1, 0, 1, 0};//对应四个移动方向
vector<vector<int>> dp(m * n, vector<int>(m * n, INT_MAX));//初始化二维dp数组
deque<pair<int, int>> q;//状态队列
dp[sx * n + sy][bx * n + by] = 0; // 初始位置的dp初始化，未进行任何移动
q.push_back({sx * n + sy, bx * n + by});//初始状态入队
while (!q.empty()) {//广度优先搜索
auto [s1, b1] = q.front();
q.pop_front();
int sx1 = s1 / n, sy1 = s1 % n, bx1 = b1 / n, by1 = b1 % n;//一位坐标转二维
if (grid[bx1][by1] == 'T') // 箱子已被推到目标处，由于是广度优先，必然是最小代价
return dp[s1][b1];
for (int i = 0; i < 4; i++) { // 玩家向四个方向移动到另一个状态
int sx2 = sx1 + d[i], sy2 = sy1 + d[i + 1], s2 = sx2*n+sy2;//人的下一个移动位置
if (!ok(sx2, sy2)) continue; // 玩家位置不合法，不能进行该次移动
if (bx1 == sx2 && by1 == sy2) { // 如果人位置与箱子位置重叠，说明推动箱子
int bx2 = bx1 + d[i], by2 = by1 + d[i + 1], b2 = bx2*n+by2;//箱子移动方向与人一致
if (!ok(bx2, by2) || dp[s2][b2] <= dp[s1][b1] + 1) // 箱子位置不合法或状态已访问，同时剪枝避免更糟糕的状态
continue;//跳过，不能往该方向移动
dp[s2][b2] = dp[s1][b1] + 1;//状态转移
q.push_back({s2, b2});//下一个状态入队
} else {
if (dp[s2][b1] <= dp[s1][b1]) continue;//状态已访问跳过，也是进行剪枝
dp[s2][b1] = dp[s1][b1];//新的状态
q.push_front({s2, b1});//新的状态入队，这里是01广度优先精髓，入的是当前层次的队，说明与前面的节点属于同一广度（因为边权值为0），可以使得优先搜索代价小的
}
}
}
return -1;
}
};