2023-05-08 LeetCode每日一题(推箱子)
2023-05-08每日一题
一、题目编号
1263. 推箱子
二、题目链接
三、题目描述
推箱子」是一款风靡全球的益智小游戏,玩家需要将箱子推到仓库中的目标位置。
游戏地图用大小为 m x n 的网格 grid 表示,其中每个元素可以是墙、地板或者是箱子。
现在你将作为玩家参与游戏,按规则将箱子 ‘B’ 移动到目标位置 ‘T’ :
- 玩家用字符 ‘S’ 表示,只要他在地板上,就可以在网格中向上、下、左、右四个方向移动。
- 地板用字符 ‘.’ 表示,意味着可以自由行走。
- 墙用字符 ‘#’ 表示,意味着障碍物,不能通行。
- 箱子仅有一个,用字符 ‘B’ 表示。相应地,网格上有一个目标位置 ‘T’。
- 玩家需要站在箱子旁边,然后沿着箱子的方向进行移动,此时箱子会被移动到相邻的地板单元格。记作一次「推动」。
- 玩家无法越过箱子。
返回将箱子推到目标位置的最小 推动 次数,如果无法做到,请返回 -1。
四、解题代码
class Solution {
int dir[4][2] ={
{-1, 0},
{1, 0},
{0, 1},
{0, -1},
};
public:
int minPushBox(vector<vector<char>>& grid) {
int people_x;
int people_y;
int box_x;
int box_y;
int m = grid.size();//地图行数
int n = grid[0].size();//地图列数
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
if(grid[i][j] == 'S'){
people_x = i;
people_y = j;
}
if(grid[i][j] == 'B'){
box_x = i;
box_y = j;
}
}
}
int dp[1000][1000];//dp[i][j], i表示玩家位置状态, j表示箱子的位置
for(int i = 0; i < 1000; ++i){
for(int j = 0; j < 1000; ++j){
dp[i][j] = INT_MAX;
}
}
queue<pair<int, int>> q;
q.push({people_x * 30 + people_y, box_x * 30 + box_y});
dp[people_x * 30 + people_y][box_x * 30 + box_y] = 0;//初始状态设置为0步
while(!q.empty()){
queue<pair<int, int>> q1;
while(!q.empty()){
int now_people = q.front().first;
int now_box = q.front().second;
int now_people_x = now_people / 30;
int now_people_y = now_people % 30;
int now_box_x = now_box / 30;
int now_box_y = now_box % 30;
q.pop();
if(grid[now_box_x][now_box_y] == 'T'){
return dp[now_people][now_box];
}
for(int i = 0; i < 4; ++i){
int next_people_x = now_people_x + dir[i][0];
int next_people_y = now_people_y + dir[i][1];
int next_people = next_people_x * 30 + next_people_y;
if(next_people_x < 0 || next_people_x >= m || next_people_y < 0 || next_people_y >= n ||
grid[next_people_x][next_people_y] == '#'){//人移动位置不合法
continue;
}
int next_box;
if(now_box_x == next_people_x && now_box_y == next_people_y){//此时推动箱子
int next_box_x = now_box_x + dir[i][0];
int next_box_y = now_box_y + dir[i][1];
next_box = next_box_x * 30 + next_box_y;
if(next_box_x < 0 || next_box_x >= m || next_box_y < 0 || next_box_y >= n ||
grid[next_box_x][next_box_y] == '#' || dp[next_people][next_box] <= dp[now_people][now_box] + 1){
//箱子移动位置不合法或者移动到该位置不满足最少推动次数
continue;
}
dp[next_people][next_box] = dp[now_people][now_box] + 1;
q1.push({next_people, next_box});
} else{
if(dp[next_people][now_box] <= dp[now_people][now_box]){
continue;
} else{
dp[next_people][now_box] = dp[now_people][now_box];
q.push({next_people, now_box});
}
}
}
}
q.swap(q1);
}
return -1;
}
};
五、解题思路
(1) 首先,我们推箱子是在平面图形中进行移动的,那么一定涉及到x坐标和y坐标,那么就需要使用点的一维表示方法。已知数组的长和宽都不超过20,那么我们已知该数组中的一个位置为(x ,y)。那么我们可以用num = x * 30 + y来表示一个点。x = num / 30, y = num % 30。
(2) 该题目思考贪心解法或者动态规划解法是不可能的,只能采用广度优先搜索和深度优先搜索来寻找。我们本题采用广度优先搜索,在平面上使用广度优先搜索方法就需要考虑四方向遍历,因为四方向遍历已经在其他题目中有所阐述,且并非本题目关键,就不再赘述。
(3) 使用广度优先搜索,广度优先搜索需要配合队列和哈希表。本题目的哈希表用在dp[1000][1000]中,dp[i][j],i表示人所处在的位置,j表示箱子所处在的位置,那么dp[i][j]就代表了一种状态,即人在i处,箱子在j处的时候,此时箱子最小推动多少下。那么一开始dp数组所有元素都应该设置成一个最大值,只有初始的位置为0步,并且把初始状态压入队列q中。
(4) 开始广搜,先从队列q的队首获取当前人所处的x坐标,y坐标,当前箱子所处的x坐标,y坐标。首先先判断箱子是否抵达终点,如果抵达了,返回dp数组中记录的次数。然后通过四方向遍历,获取下一步的人的x坐标和y坐标,然后判断该人所处的位置是否合法,如果不合法(超出边界或者穿墙了)则跳过,否则的话则需要判断是否移动到箱子的位置,如果没有移动到箱子的位置则需要判断当前状态是否有更小推箱子次数,如果存在了更少的可能性则排除,否则的话记录该状态并且加入到q队列中。如果移动到箱子的位置,则箱子也需要同方向移动一格,然后判断箱子移动的情况(是否合法,是否有同位置推箱子次数更少的可能性)如果有的话则跳过,否则的话更新该状态并且将该状态压入到q1队列中(q1队列是一个新队列)。
(5) 最后q为空则将q1和q对换,如果此时q还是为空,则代表所有情况都已经搜索完毕了。
(6) 如果所用情况都搜索完毕仍然没有结果的话,那么就返回-1,意味着无法将箱子推到终点。