文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 超時(shí)解
    • 2.2 BFS + DFS

1. 題目

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

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

現(xiàn)在你將作為玩家參與游戲，按規(guī)則將箱子 'B' 移動(dòng)到目標(biāo)位置 'T' ：

• 玩家用字符 'S' 表示，只要他在地板上，就可以在網(wǎng)格中向上、下、左、右四個(gè)方向移動(dòng)。
• 地板用字符 '.' 表示，意味著可以自由行走。
• 墻用字符 '#' 表示，意味著障礙物，不能通行。
• 箱子僅有一個(gè)，用字符 'B' 表示。相應(yīng)地，網(wǎng)格上有一個(gè)目標(biāo)位置 'T'。

玩家需要站在箱子旁邊，然后沿著箱子的方向進(jìn)行移動(dòng)，此時(shí)箱子會(huì)被移動(dòng)到相鄰的地板單元格。記作一次「推動(dòng)」。
玩家無法越過箱子。
返回將箱子推到目標(biāo)位置的最小 推動(dòng) 次數(shù)，如果無法做到，請(qǐng)返回 -1。

示例 1：

輸入：grid = [["#","#","#","#","#","#"],["#","T","#","#","#","#"],["#",".",".","B",".","#"],["#",".","#","#",".","#"],["#",".",".",".","S","#"],["#","#","#","#","#","#"]] 輸出：3 解釋：我們只需要返回推箱子的次數(shù)。示例 2： 輸入：grid = [["#","#","#","#","#","#"],["#","T","#","#","#","#"],["#",".",".","B",".","#"],["#","#","#","#",".","#"],["#",".",".",".","S","#"],["#","#","#","#","#","#"]] 輸出：-1示例 3： 輸入：grid = [["#","#","#","#","#","#"],["#","T",".",".","#","#"],["#",".","#","B",".","#"],["#",".",".",".",".","#"],["#",".",".",".","S","#"],["#","#","#","#","#","#"]] 輸出：5 解釋：向下、向左、向左、向上再向上。示例 4： 輸入：grid = [["#","#","#","#","#","#","#"],["#","S","#",".","B","T","#"],["#","#","#","#","#","#","#"]] 輸出：-1提示： 1 <= grid.length <= 20 1 <= grid[i].length <= 20 grid 僅包含字符 '.', '#', 'S' , 'T', 以及 'B'。 grid 中 'S', 'B' 和 'T' 各只能出現(xiàn)一個(gè)。

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

2. 解題

2.1 超時(shí)解

15 / 18 個(gè)通過測(cè)試用例

• 優(yōu)先隊(duì)列里存入 box 和 人的4個(gè)坐標(biāo)位置，以及推的次數(shù)，推的次數(shù)小的優(yōu)先
• 隊(duì)列里存了太多的狀態(tài)

class node { public:int push, bi, bj, pi, pj;node(int n, int a, int b, int c, int d){push = n;bi = a;bj = b;pi = c;pj = d;} }; struct hashf // 自定義哈希 {unsigned long long operator()(node v) const{return 1ULL*v.push*pow(21,4)+v.bi*pow(21,3)+v.bj*pow(21,2)+v.pi*21+v.pj;} }; struct eqf // 哈希set 相等判斷函數(shù) {bool operator()(node v1, node v2) const//不能寫引用，會(huì)報(bào)錯(cuò){return v1.push==v2.push && v1.bi==v2.bi && v1.bj==v2.bj&& v1.pi==v2.pi && v1.pj==v2.pj;} }; struct cmp {bool operator()(node& a, node& b) const{return a.push > b.push;//推得次數(shù)少的優(yōu)先} }; class Solution { public:int minPushBox(vector<vector<char>>& grid) {int m = grid.size(), n = grid[0].size(), k = 21;int targetx, targety, boxi, boxj, peoplei, peoplej, push = 0, size;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 'S')peoplei = i, peoplej = j;else if(grid[i][j] == 'B')boxi = i, boxj = j;else if(grid[i][j] == 'T')targetx = i, targety = j;}}vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};priority_queue<node, vector<node>, cmp> q; node state(0, boxi, boxj, peoplei, peoplej);q.push(state);unordered_set<node, hashf, eqf> vis;vis.insert(state);while(!q.empty()){int pj = q.top().pj;int pi = q.top().pi;int bj = q.top().bj;int bi = q.top().bi;push = q.top().push;if(bi==targetx && bj==targety)return push;q.pop();int nextbi, nextbj, nextpi, nextpj;for(int d = 0; d < 4; d++){nextpi = pi+dir[d][0];nextpj = pj+dir[d][1];state.push = push;if(nextpi==bi && nextpj==bj){ // 推動(dòng)箱子了nextbi = bi+dir[d][0];nextbj = bj+dir[d][1];state.push++;}else{nextbi = bi;nextbj = bj;}state.bi = nextbi;state.bj = nextbj;state.pi = nextpi;state.pj = nextpj;if(nextpi>=0 && nextpi<m && nextpj>=0 && nextpj<n &&nextbi>=0 && nextbi<m && nextbj>=0 && nextbj<n &&grid[nextpi][nextpj] != '#' && grid[nextbi][nextbj] != '#' &&vis.find(state) == vis.end()){vis.insert(state);q.push(state);}}}return -1;} };

2.2 BFS + DFS

• 隊(duì)列里面只存能推動(dòng)箱子的狀態(tài)
• 中間到達(dá)推箱子的過程，不必記錄到隊(duì)列內(nèi)，采用DFS判斷人的位置能否到達(dá)推動(dòng)箱子的位置
• 不采用優(yōu)先隊(duì)列也可以

class node { public:int push, bi, bj, pi, pj;node(int n, int a, int b, int c, int d){push = n;bi = a;bj = b;pi = c;pj = d;} }; struct hashf {unsigned long long operator()(node v) const{return 1ULL*v.bi*pow(21,3)+v.bj*pow(21,2)+v.pi*21+v.pj;} }; struct eqf {bool operator()(node v1, node v2) const//不能寫引用{return v1.bi==v2.bi && v1.bj==v2.bj&& v1.pi==v2.pi && v1.pj==v2.pj;//2個(gè)物品的位置都相等即set中出現(xiàn)過了} }; struct cmp {bool operator()(node& a, node& b) const{return a.push > b.push;//推得次數(shù)少的優(yōu)先} }; class Solution {vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}}; public:int minPushBox(vector<vector<char>>& grid) {int m = grid.size(), n = grid[0].size();int targetx, targety, boxi, boxj, peoplei, peoplej, push = 0, size;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 'S')peoplei = i, peoplej = j;else if(grid[i][j] == 'B')boxi = i, boxj = j;else if(grid[i][j] == 'T')targetx = i, targety = j;}}priority_queue<node, vector<node>, cmp> q; node state(0, boxi, boxj, peoplei, peoplej);q.push(state);unordered_set<node, hashf, eqf> vis;vis.insert(state);while(!q.empty()){int pj = q.top().pj;int pi = q.top().pi;int bj = q.top().bj;int bi = q.top().bi;push = q.top().push;if(bi==targetx && bj==targety)return push;q.pop();int nextbi, nextbj, nextpi, nextpj, pushPosx, pushPosy;for(int d = 0; d < 4; d++){nextbi = bi+dir[d][0];nextbj = bj+dir[d][1];if(nextbi<0 || nextbi>=m || nextbj<0 || nextbj>=n || grid[nextbi][nextbj] == '#')continue; // 箱子下一個(gè)位置不合法nextpi = bi;nextpj = bj;pushPosx = bi-dir[d][0];//人推動(dòng)箱子前的位置pushPosy = bj-dir[d][1];if(pushPosx<0 || pushPosx>=m || pushPosy<0 || pushPosy>=n || grid[pushPosx][pushPosy] == '#')continue; // 推箱子位置不合法vector<vector<bool>> record(m, vector<bool>(n, false));if(!canReachPushPos(grid,pi,pj,bi,bj,pushPosx,pushPosy,record))continue;//不能從當(dāng)前位置到達(dá)推箱子位置state.push = push+1;state.bi = nextbi;state.bj = nextbj;state.pi = nextpi;state.pj = nextpj;if(vis.find(state) == vis.end()){vis.insert(state);q.push(state);}}}return -1;}bool canReachPushPos(vector<vector<char>>& grid, int x0, int y0, int bi, int bj, int tx, int ty, vector<vector<bool>>& vis){vis[x0][y0] = true;if(x0==tx && y0==ty) return true;int m = grid.size(), n = grid[0].size();for(int k = 0; k < 4; k++){int nx = x0+dir[k][0];int ny = y0+dir[k][1];if(nx>=0 && nx<m && ny>=0 && ny<n && grid[nx][ny] != '#' && !(nx==bi && ny==bj) && !vis[nx][ny]){ // box 也不能穿過if(canReachPushPos(grid,nx, ny,bi,bj,tx,ty, vis))return true;}}return false;} };

240 ms 20.4 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1263. 推箱子（BFS+DFS / 自定义哈希set）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。