题目描述
Storekeeper is a game, in which the player pushes boxes around in a warehouse, trying to get them to target locations.
The game is represented by a grid
of size n*``m
, where each element is a wall, floor or a box.
Your task is move the box 'B'
to the target position 'T'
under the following rules:
- Player is represented by character
'S'
and can move up, down, left, right in thegrid
if its a floor (empy cell). - Floor is represented by character
'.'
that means free cell to walk. - Wall is represented by character
'#'
that means obstacle (impossible to walk there). - There is only one box
'B'
and one target cell'T'
in thegrid
. - The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push.
- The player cannot walk through the box.
Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1
.
Example 1:
Input: grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#",".","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output: 3
Explanation: We return only the number of times the box is pushed.
Example 2:
Input: grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#","#","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output: -1
Example 3:
Input: grid = [["#","#","#","#","#","#"],
["#","T",".",".","#","#"],
["#",".","#","B",".","#"],
["#",".",".",".",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output: 5
Explanation: push the box down, left, left, up and up.
Example 4:
Input: grid = [["#","#","#","#","#","#","#"],
["#","S","#",".","B","T","#"],
["#","#","#","#","#","#","#"]]
Output: -1
Constraints:
1 <= grid.length <= 20
1 <= grid[i].length <= 20
grid
contains only characters'.'
,'#'
,'S'
,'T'
, or'B'
.- There is only one character
'S'
,'B'
and'T'
in thegrid
.
题意:「推箱子」是一款风靡全球的益智小游戏,玩家需要将箱子推到仓库中的目标位置。
游戏地图用大小为 n * m
的网格 grid
表示,其中每个元素可以是墙、地板或者是箱子。
现在你将作为玩家参与游戏,按规则将箱子 ‘B’ 移动到目标位置 ‘T’ :
- 玩家用字符 ‘S’ 表示,只要他在地板上,就可以在网格中向上、下、左、右四个方向移动。
- 地板用字符 ‘.’ 表示,意味着可以自由行走。
- 墙用字符 ‘#’ 表示,意味着障碍物,不能通行。
- 箱子仅有一个,用字符 ‘B’ 表示。相应地,网格上有一个目标位置 ‘T’。
玩家需要站在箱子旁边,然后沿着箱子的方向进行移动,此时箱子会被移动到相邻的地板单元格。记作一次「推动」。玩家无法越过箱子。
返回将箱子推到目标位置的最小 推动 次数,如果无法做到,请返回 -1。
算法1
(BFS)
题解:(4-12ms,beats 98% - 100%)。
这道题算然代码量比较大,但是其实是一个纸老虎,只要我们抓住BFS的本质即可。我们首先使用terminal,box,person
三个变量保存终点位置,箱子位置,人的初始位置(坐标压缩表示),同时将对应的位置上的点变成.
,方便后面的BFS。
我们接下来只需要箱子能够往哪些位置推即可:如果想往上推,需要满足的条件有:
- 目标位置没有越界,没有障碍。
- 当前箱子下面的位置没有越界,没有障碍。
- 人能够从当前位置走到当前箱子下面的位置。
- 该状态没有被搜索过。
对于条件一和条件二,我们很好判断。对于条件三,我们单独使用一个BFS来判断能否走到箱子下面的位置,这里因为人不能够越过箱子,所以箱子在这个BFS中也是一个障碍。
对于条件四,我们使用二维状态来表示:visit[box][dir]
,其中box
表示当前箱子的位置,dir
表示箱子最后一步是如何推的,这里分别使用0,1,2,3
代表上,右,下,左四个方向。
思路理顺了之后,就是常规的BFS了,这里BFS队列中不仅要存储箱子位置,也要存储人的位置,这里我们使用pair<int,int>
来存储,然后依次枚举四个方向能否推到即可。
class Solution {
public:
int n,m,dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
bool checkMove(int person,int target,int box,vector<vector<char>>& grid)
{
int visit[n][m] = {};
if(person == target) return true;
queue<int> q;
q.push(person);
visit[person / m][person % m] == 1;
while(!q.empty())
{
int p = q.front(),r = p / m ,c = p % m;
q.pop();
for(int i = 0 ; i < 4 ; i ++)
{
int x = r + dx[i],y = c + dy[i],idx = x * m + y;
if(x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == '.' && visit[x][y] == 0 && idx != box)
{
if(idx == target) return true;
q.push(idx);
visit[x][y] = 1;
}
}
}
return false;
}
int minPushBox(vector<vector<char>>& grid) {
n = grid.size(), m = grid[0].size();
int terminal,box,person;
for(int i = 0 ; i < n ; i ++)
{
for(int j = 0 ; j < m ; j ++)
{
if(grid[i][j] == 'T') terminal = i * m + j;
else if(grid[i][j] == 'B') box = i * m + j;
else if(grid[i][j] == 'S') person = i * m + j;
if(grid[i][j] != '#') grid[i][j] = '.';
}
}
queue<pair<int,int>> q;
int visit[400][4] = {};
q.push({box,person});
int res = 1,size = 1;
while(!q.empty())
{
while(size --)
{
auto p = q.front();
int cur_box = p.first,cur_person = p.second,r = cur_box / m,c = cur_box % m;
q.pop();
for(int i = 0 ; i < 4 ; i ++)
{
int x = r + dx[i],y = c + dy[i],idx = x * m + y;
int person_x = x - 2 * dx[i],person_y = y - 2 * dy[i],next_person = person_x * m + person_y;
if(x >= 0 && x < n && y >= 0 && y < m && person_x >= 0 && person_x < n && person_y >= 0 && person_y < m && grid[x][y] == '.' && grid[person_x][person_y] == '.' && visit[idx][i] == 0 && checkMove(cur_person,next_person,cur_box,grid) )
{
if(idx == terminal) return res;
q.push({idx,next_person});
visit[idx][i] = 1;
}
}
if(size == 0)
{
size = q.size();
res ++;
}
}
}
return -1;
}
};
作者大大,if (size == 0){size = q.size(); res++},这句话什么意思啊?
这个是BFS题目在求最短步骤常用的方法,size代表的是当前层还没有被搜索的状态,当size=0的时候,说明当前层已经被搜索完了,我们开始搜索下一层,下一层的状态数就是当前队列中的状态数。
size = q.size()我可以理解,但是为什么可以res++了啊?还有res的初始值为什么是1?
注意我们return res;语句的位置。我们最开始是从初始状态,如果只经过一步就可以推到终点,如果res = 0就直接返回0了,这是不正确的。res 的意思是,我们第k步能够到达的若干种状态都没有到达终点,现在我们要从第k步能够到达的若干种状态继续搜索,这时候就是第k + 1步了。所以res 。