題目：
「推箱子」是一款風(fēng)靡全球的益智小游戲，玩家需要將箱子推到倉庫中的目標位置。

游戲地圖用大小為 m x n 的網(wǎng)格 grid 表示，其中每個元素可以是墻、地板或者是箱子。

現(xiàn)在你將作為玩家參與游戲，按規(guī)則將箱子 ‘B’ 移動到目標位置 ‘T’ ：

玩家用字符 ‘S’ 表示，只要他在地板上，就可以在網(wǎng)格中向上、下、左、右四個方向移動。
地板用字符 ‘.’ 表示，意味著可以自由行走。
墻用字符 ‘#’ 表示，意味著障礙物，不能通行。
箱子僅有一個，用字符 ‘B’ 表示。相應(yīng)地，網(wǎng)格上有一個目標位置 ‘T’。
玩家需要站在箱子旁邊，然后沿著箱子的方向進行移動，此時箱子會被移動到相鄰的地板單元格。記作一次「推動」。
玩家無法越過箱子。
返回將箱子推到目標位置的最小 推動 次數(shù)，如果無法做到，請返回 -1。

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/minimum-moves-to-move-a-box-to-their-target-location
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

題意：
規(guī)則其實就跟我們小時候玩的那個手機游戲–推箱子是一樣的。

思路：
這道題其實思路很簡單，和走迷宮是一個道理的，當你把箱子和人看成一個整體的時候，就是走迷宮，那直接搜索就可以解決了。

而這道題的不同之處在于，還有個人的位置要考慮。也就是從人出發(fā)，向四個方向搜索，如果人移動之后的位置是墻，那就是不合法的，回到上個狀態(tài)搜索；如果人移動之后的位置是箱子的位置，就說明是合法的，然后將箱子進行對應(yīng)的移動，判斷是否合法，合法的話就存到q1隊列中。那還有一種情況是人移動之后的位置不是墻也不是箱子的位置，那就用能走到此位置的最小值來更新它。因為我們最后的答案就是dp【】【】數(shù)組，所以這個值不能忽略，仍然要賦值。

詳細的講解如下：
n 是地圖的列數(shù) ， m 是地圖的行數(shù)。
solve（）函數(shù)是用來判斷 x ， y 的位置是否合法。
sx，sy是人的位置。
bx，by是箱子的位置。
dp【i】【j】表示人在 i 位置箱子在 j 位置的最小步數(shù)。

首先將dp初始化為999999，然后將人的初始位置賦值為0.

然后將初始位置放入隊列。

首先第一層循環(huán)，隊列不為空的話：
新開一個隊列 q1 ， 用來存放從 q 中拿出的位置向四個方向移動后的合法位置。

sx1，sy1是對頭的人的位置，bx1，by1是對頭的箱子的位置。

如果此時箱子的位置是終點，那說明這個位置已經(jīng)到達終點，dp[s1][b1]就是答案。

不是終點的話，像四個方向探索：
sx2，sy2是sx1，sy1移動后的人的位置，bx2，by2是bx1，by1移動后的箱子的位置。

首先判斷sx2，sy2是否合法，不合法的話就下一個方向，合法的話判斷，sx2，sy2人的位置是否和箱子的位置bx1，by1重合，重合的話才是真正意義上的推動箱子，就將箱子向同一方向移動，如果移動后的箱子的位置bx2，by2也合法的話，那dp【s2】【b2】的步數(shù)就是dp【s1】【b1】的步數(shù)加一，并將s2，b2加到q1中，因為他是新的合法的位置。

q遍歷完，將q1的值賦給q，然后接著遍歷q。這里q1的意義在于，因為我們是兩層遍歷q的循環(huán)，如果不設(shè)置q1的話，會造成循環(huán)的次序錯誤。

代碼：文章來源地址http://www.zghlxwxcb.cn/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;
    }
};

到了這里，關(guān)于1263. 推箱子的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！