题目：
「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。
游戏地图用大小为 m x n 的网格 grid 表示，其中每个元素可以是墙、地板或者是箱子。
现在你将作为玩家参与游戏，按规则将箱子 ‘B’ 移动到目标位置 ‘T’ ：
玩家用字符 ‘S’ 表示，只要他在地板上，就可以在网格中向上、下、左、右四个方向移动。
地板用字符 ‘.’ 表示，意味着可以自由行走。
墙用字符 ‘#’ 表示，意味着障碍物，不能通行。
箱子仅有一个，用字符 ‘B’ 表示。相应地，网格上有一个目标位置 ‘T’。
玩家需要站在箱子旁边，然后沿着箱子的方向进行移动，此时箱子会被移动到相邻的地板单元格。记作一次「推动」。
玩家无法越过箱子。
返回将箱子推到目标位置的最小 推动 次数，如果无法做到，请返回 -1。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-moves-to-move-a-box-to-their-target-location
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题意：
规则其实就跟我们小时候玩的那个手机游戏–推箱子是一样的。
思路：
这道题其实思路很简单，和走迷宫是一个道理的，当你把箱子和人看成一个整体的时候，就是走迷宫，那直接搜索就可以解决了。
而这道题的不同之处在于，还有个人的位置要考虑。也就是从人出发，向四个方向搜索，如果人移动之后的位置是墙，那就是不合法的，回到上个状态搜索；如果人移动之后的位置是箱子的位置，就说明是合法的，然后将箱子进行对应的移动，判断是否合法，合法的话就存到q1队列中。那还有一种情况是人移动之后的位置不是墙也不是箱子的位置，那就用能走到此位置的最小值来更新它。因为我们最后的答案就是dp【】【】数组，所以这个值不能忽略，仍然要赋值。
详细的讲解如下：
n 是地图的列数 ， m 是地图的行数。
solve（）函数是用来判断 x ， y 的位置是否合法。
sx，sy是人的位置。
bx，by是箱子的位置。
dp【i】【j】表示人在 i 位置箱子在 j 位置的最小步数。
首先将dp初始化为999999，然后将人的初始位置赋值为0.
然后将初始位置放入队列。
首先第一层循环，队列不为空的话：
新开一个队列 q1 ， 用来存放从 q 中拿出的位置向四个方向移动后的合法位置。
sx1，sy1是对头的人的位置，bx1，by1是对头的箱子的位置。
如果此时箱子的位置是终点，那说明这个位置已经到达终点，dp[s1][b1]就是答案。
不是终点的话，像四个方向探索：
sx2，sy2是sx1，sy1移动后的人的位置，bx2，by2是bx1，by1移动后的箱子的位置。
首先判断sx2，sy2是否合法，不合法的话就下一个方向，合法的话判断，sx2，sy2人的位置是否和箱子的位置bx1，by1重合，重合的话才是真正意义上的推动箱子，就将箱子向同一方向移动，如果移动后的箱子的位置bx2，by2也合法的话，那dp【s2】【b2】的步数就是dp【s1】【b1】的步数加一，并将s2，b2加到q1中，因为他是新的合法的位置。
q遍历完，将q1的值赋给q，然后接着遍历q。这里q1的意义在于，因为我们是两层遍历q的循环，如果不设置q1的话，会造成循环的次序错误。文章来源：https://www.toymoban.com/news/detail-684812.html
代码：文章来源地址https://www.toymoban.com/news/detail-684812.html
class Solution {
public:
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int n , m;
bool solve(vector<vector<char>>& g , int& x , int& y){
if(x < 0 || y < 0 || x >= m || y >= n || g[x][y] == '#')
return false;
return true;
}
int minPushBox(vector<vector<char>>& grid) {
m = grid.size();
n = grid[0].size();
int sx , sy , bx , by;
for(int i = 0 ; i < m ; i++){
for(int j = 0 ; j < n ; j++){
if(grid[i][j] == 'S'){
sx = i;
sy = j;
}
else if(grid[i][j] == 'B'){
bx = i;
by = j;
}
}
}
int dp[1010][1010];
for(int i = 0 ; i < 1010 ; i++){
for(int j = 0 ; j < 1010 ; j++){
dp[i][j] = 9999999;
}
}
queue<pair<int,int>> q;
dp[sx*n + sy][bx*n + by] = 0;
q.push({sx*n+sy , bx*n+by});
while(!q.empty()){
queue<pair<int , int>> q1;
while(!q.empty()){
auto [s1,b1] = q.front();
q.pop();
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 + dir[i][0];
int sy2 = sy1 + dir[i][1];
int s2 = sx2*n+sy2;
if(!solve(grid , sx2 , sy2))
continue;
if(bx1 == sx2 && by1 == sy2){
int bx2 = bx1 + dir[i][0];
int by2 = by1 + dir[i][1];
int b2 = bx2*n + by2;
if(!solve(grid , bx2 , by2) || dp[s2][b2] <= dp[s1][b1]+1)
continue;
dp[s2][b2] = dp[s1][b1] + 1;
q1.push({s2 , b2});
}
else{
if(dp[s2][b1] <= dp[s1][b1])
continue;
dp[s2][b1] = dp[s1][b1];
q.push({s2 , b1});
}
}
}
q.swap(q1);
}
return -1;
}
};
到了这里，关于1263. 推箱子的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
