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

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

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

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

示例 1：

輸入：grid = [[“#”,“#”,“#”,“#”,“#”,“#”],
[“#”,“T”,“#”,“#”,“#”,“#”],
[“#”,“.”,“.”,“B”,“.”,“#”],
[“#”,“.”,“#”,“#”,“.”,“#”],
[“#”,“.”,“.”,“.”,“S”,“#”],
[“#”,“#”,“#”,“#”,“#”,“#”]]
輸出：3
解釋：我們只需要返回推箱子的次數(shù)。
示例 2：

輸入：grid = [[“#”,“#”,“#”,“#”,“#”,“#”],
[“#”,“T”,“#”,“#”,“#”,“#”],
[“#”,“.”,“.”,“B”,“.”,“#”],
[“#”,“#”,“#”,“#”,“.”,“#”],
[“#”,“.”,“.”,“.”,“S”,“#”],
[“#”,“#”,“#”,“#”,“#”,“#”]]
輸出：-1
示例 3：

輸入：grid = [[“#”,“#”,“#”,“#”,“#”,“#”],
[“#”,“T”,“.”,“.”,“#”,“#”],
[“#”,“.”,“#”,“B”,“.”,“#”],
[“#”,“.”,“.”,“.”,“.”,“#”],
[“#”,“.”,“.”,“.”,“S”,“#”],
[“#”,“#”,“#”,“#”,“#”,“#”]]
輸出：5
解釋：向下、向左、向左、向上再向上。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 20
grid 僅包含字符 ‘.’, ‘#’, ‘S’ , ‘T’, 以及 ‘B’。
grid 中 ‘S’, ‘B’ 和 ‘T’ 各只能出現(xiàn)一個。

這道題和上周華為暑期實習筆試的第三題有點相似，但個人感覺這道題難度更大。首先給這道題扣個帽子，屬于一道搜索，但是不同于一般的搜索，這道題的搜索過程明顯要麻煩一些。先說一下自己之前的錯誤思路：
①將整個問題分解為兩個問題：人如何到達箱子邊下以及箱子如何再到達終點。
②以人為起點進行廣搜，當和箱子相遇之后就合為一體。
對于第一個思路，錯誤之處在于這是一個整體考慮的問題，并不是單獨拆分就可以實現(xiàn)的，整體的最優(yōu)值并不一定完全等于拆分后的最優(yōu)值。而對于第二個思路，完全是讀錯了題目，題目要求的是，要計算推動箱子的次數(shù)，人推一下箱子之后，完全可以離開箱子跑到另一個位置來推。

最近一直在干組里的活，沒時間仔細研究這道題，所以參考題解寫了一版自己的代碼。根據(jù)官方給的題解，這道題可以看作是一個復雜狀態(tài)下的廣搜，為什么說復雜呢，一般的廣搜我們只需要考慮行動者的狀態(tài)，一般就是那個能移動的個體，但是這道題，我們還需要將狀態(tài)擴展為人和箱子的狀態(tài)，箱子在不同的位置時，人即使坐標一樣，也代表不同的狀態(tài)。我們依然是以人為行動者，向四個方向進行搜索，當人的位置與當前箱子的位置重合，說明人推到了箱子，此時按照人移動的方向對箱子進行同樣的移動，同時對狀態(tài)數(shù)組進行增加來表示推過了一次箱子。此外，與一般的廣度優(yōu)先搜索不同，我們不能使用flag來標記哪些地方走過了哪些沒走過，因為推動箱子之后可能存在更換方向推動箱子的情況，根據(jù)題解的方法，當我們推動箱子時，狀態(tài)的改變會存入另一個隊列，在下一輪循環(huán)中再進行廣搜。

int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int step[25][25][25][25];

int height, length;

int minPushBox(vector<vector<char> >& grid) {
	int sx, sy, ex, ey, bx, by;

	height = grid.size();
	length = grid[0].size();
	for(int i=0; i<height; i++){
		for(int j=0; j<length; j++){
			for(int m=0; m<height; m++){
				for(int n=0; n<length; n++){
					step[i][j][m][n] = INT_MAX;
				}
			}
		}
	}
	for(int i=0; i<height; i++){
		for(int j=0; j<length; j++){
			char c = grid[i][j];
			
			if(c=='S'){
				sx = i;
				sy = j;
			}
			if(c=='T'){
				ex = i;
				ey = j;
			}
			if(c=='B'){
				bx = i;
				by = j;
			}
		}
	}
	step[sx][sy][bx][by] = 0;
	queue<pair<pair<int, int>, pair<int, int> > > q;
	q.push(make_pair(make_pair(sx, sy), make_pair(bx, by)));
	while(!q.empty()){
		queue<pair<pair<int, int>, pair<int, int> > > q1;
		while(!q.empty()){
			pair<pair<int, int>, pair<int, int> > temp = q.front();
			q.pop();
			
			int npx = temp.first.first;
			int npy = temp.first.second;
			int nbx = temp.second.first;
			int	nby = temp.second.second;
			if(nbx==ex && nby==ey)
				return step[npx][npy][nbx][nby];
			
			for(int i=0; i<4; i++){
				int tpx = npx + dir[i][0];
				int tpy = npy + dir[i][1];
				 
				if(tpx<0||tpy<0||tpx>=height||tpy>=length||grid[tpx][tpy]=='#')
					continue;
				if(tpx==nbx && tpy==nby){
					// 推到了箱子 
					int tbx = nbx + dir[i][0];
					int tby = nby + dir[i][1];
					if(tbx<0||tby<0||tbx>=height||tby>=length||grid[tbx][tby]=='#')
						continue;
						
					if(step[tpx][tpy][tbx][tpy] <= step[npx][npy][nbx][nby] + 1)
						continue;
					
					step[tpx][tpy][tbx][tby] = step[npx][npy][nbx][nby] + 1;
					
					q1.push(make_pair(make_pair(tpx, tpy), make_pair(tbx, tby)));
				}else{
					// 沒有推到箱子 
					if(step[tpx][tpy][nbx][nby] <= step[npx][npy][nbx][nby])
						continue;
					step[tpx][tpy][nbx][nby] = step[npx][npy][nbx][nby];
					q.push(make_pair(make_pair(tpx, tpy), make_pair(nbx, nby)));
				}	
			}
		}
		q.swap(q1);
	}
	return -1;
}

相比于題解的代碼，我稍微改了一下數(shù)據(jù)結構的寫法，按道理理解起來要稍微容易那么一點點，但是內存開銷增加了不少，題解用的是一個數(shù)來表示二維的坐標，在定位以及四方向移動時會稍微麻煩點，所以我直接換成了四維數(shù)組，前兩維表示人的位置，后兩維表示箱子的位置，思路還是按照題解的思路。從人的位置開始四方向搜索，位置合法的情況下，判斷是否與箱子的坐標產生了重疊，如果沒有，那就繼續(xù)搜索，但是在繼續(xù)搜索的時候，為了避免重復走的問題，我們需要用step進行去重，也就是step[tpx][tpy][nbx][nby] <= step[npx][npy][nbx][nby]這個條件，這個條件實際上是在說，我們按照某個路徑一直搜，搜索到頭發(fā)現(xiàn)是個死路，如果不加這個條件，我們就會按照原路返回從而死循環(huán)，由于一開始我們設定了step的值全是最大值，只把起始位置改成了0，也就是說在第一輪搜索的過程中，所有走過的位置都改成了0，此時當走到死路的時候，就可以利用這個條件避免重走回頭路。但是如果這個過程我們推到了箱子，事情就是另一回事了，我們推到了箱子，再走回頭路就是允許的，因為此時我們可能是在利用回頭路移動到箱子的另一個方向，但是回頭路的回頭路依然是不允許的，回頭路的回頭路依然是用step[tpx][tpy][nbx][nby] <= step[npx][npy][nbx][nby]進行篩選。值得一提的是，我們推到箱子之后，用q1進行了單獨存儲，這本質上是想讓推到箱子作為開啟下一次循環(huán)。我們每次循環(huán)，是從上一次的狀態(tài)，在不走重復路的基礎上，遍歷所有路徑找到能夠推到箱子的新狀態(tài)，下次在這部分的狀態(tài)上進行繼續(xù)的搜索。文章來源地址http://www.zghlxwxcb.cn/news/detail-442317.html

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