题目描述
推箱子游戏中,玩家需要将箱子推到仓库中的目标位置。
游戏地图用大小为 n * m
的网格 grid
表示,其中每个元素可以是墙、地板或者是箱子。
现在你将作为玩家参与游戏,按规则将箱子 'B'
移动到目标位置 'T'
:
- 玩家用字符
'S'
表示,只要他在地板上,就可以在网格中向上、下、左、右四个方向移动。 - 地板用字符
'.'
表示,意味着可以自由行走。 - 墙用字符
'#'
表示,意味着障碍物,不能通行。 - 箱子仅有一个,用字符
'B'
表示。相应地,网格上有一个目标位置'T'
。 - 玩家需要站在箱子旁边,然后沿着箱子的方向进行移动,此时箱子会被移动到相邻的地板单元格。记作一次 推动。
- 玩家无法越过箱子。
返回将箱子推到目标位置的最小 推动 次数,如果无法做到,请返回 -1
。
样例
输入:grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#",".","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
输出:3
解释:我们只需要返回推箱子的次数。
输入:grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#","#","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
输出:-1
输入:grid = [["#","#","#","#","#","#"],
["#","T",".",".","#","#"],
["#",".","#","B",".","#"],
["#",".",".",".",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
输出:5
解释:向下、向左、向左、向上再向上。
输入:grid = [["#","#","#","#","#","#","#"],
["#","S","#",".","B","T","#"],
["#","#","#","#","#","#","#"]]
输出:-1
限制
1 <= grid.length <= 20
1 <= grid[i].length <= 20
grid
仅包含字符'.'
,'#'
,'S'
,'T'
, 以及'B'
。grid
中'S'
,'B'
和'T'
各只能出现一个。
算法
(宽度优先搜索) $O(n^2m^2)$
- 定义状态为一个三元组
(x, y, p)
,其中x
和y
表示箱子的坐标,p
的范围为[0, 3]
,表示在箱子的哪一侧。为了方便,此处我们规定,p=0
表示在箱子左侧,p=1
表示右侧,p=2
表示上侧,p=3
表示下侧。 - 每个状态有最多 4 种拓展方式:可以拓展
p
,即人换到箱子的其他侧,或者推动一步箱子。判断人是否能换到箱子的另一侧,需要再做一次宽度优先搜索或深度优先搜索。 - 此时这就是个边权仅为 0 和 1 的最短路问题,我们采用双端队列的实现方式,边权为 0 的拓展往队首入队,边权为 1 的拓展往队尾入队,每个状态最多入队两次。这样实现可以保证状态出队时,距离一定是最小的。
时间复杂度
- 共计有 $O(nm)$ 个状态和 $O(nm)$ 的边,每个状态的拓展需要额外 $O(nm)$ 的时间判定,故总时间复杂度为 $O(n^2m^2)$。
空间复杂度
- 需要额外 $O(nm)$ 的空间存放状态和队列。
C++ 代码
class Solution {
public:
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};
bool valid(int sx, int sy, int tx, int ty,
const vector<vector<char>> &grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> vis(n, vector<int>(m, false));
queue<pair<int, int>> q;
vis[sx][sy] = true;
q.push(make_pair(sx, sy));
while (!q.empty()) {
auto u = q.front();
q.pop();
if (u.first == tx && u.second == ty)
return true;
for (int i = 0; i < 4; i++) {
int x = u.first + dx[i], y = u.second + dy[i];
if (x < 0 || x >= n || y < 0 || y >= m
|| vis[x][y] || grid[x][y] != '.')
continue;
vis[x][y] = true;
q.push(make_pair(x, y));
}
}
return false;
}
int minPushBox(vector<vector<char>>& grid) {
int n = grid.size(), m = grid[0].size();
int bx, by, sx, sy, tx, ty;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (grid[i][j] == 'T') {
tx = i; ty = j;
grid[i][j] = '.';
} else if (grid[i][j] == 'B') {
bx = i; by = j;
grid[i][j] = '.';
} else if (grid[i][j] == 'S') {
sx = i; sy = j;
grid[i][j] = '.';
}
deque<tuple<int, int, int>> q;
vector<vector<vector<int>>> dis(n,
vector<vector<int>>(m,
vector<int>(4,
n * m * 4)));
grid[bx][by] = '#';
for (int i = 0; i < 4; i++) {
int x = bx + dx[i], y = by + dy[i];
if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '#')
continue;
if (valid(sx, sy, x, y, grid)) {
dis[bx][by][i] = 0;
q.push_front(make_tuple(bx, by, i));
}
}
grid[bx][by] = '.';
while (!q.empty()) {
auto u = q.front();
q.pop_front();
bx = get<0>(u);
by = get<1>(u);
int pos = get<2>(u);
sx = bx + dx[pos];
sy = by + dy[pos];
// 人换位置
grid[bx][by] = '#';
for (int i = 0; i < 4; i++)
if (i != pos) {
int x = bx + dx[i], y = by + dy[i];
if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '#')
continue;
if (dis[bx][by][i] > dis[bx][by][pos]
&& valid(sx, sy, x, y, grid)) {
dis[bx][by][i] = dis[bx][by][pos];
q.push_front(make_tuple(bx, by, i));
}
}
grid[bx][by] = '.';
// 推动箱子
int x = bx + dx[pos ^ 1];
int y = by + dy[pos ^ 1];
if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '#')
continue;
if (dis[x][y][pos] > dis[bx][by][pos] + 1) {
dis[x][y][pos] = dis[bx][by][pos] + 1;
q.push_back(make_tuple(x, y, pos));
}
}
int ans = n * m * 4;
for (int i = 0; i < 4; i++)
ans = min(ans, dis[tx][ty][i]);
if (ans == n * m * 4)
ans = -1;
return ans;
}
};
牛哇牛哇,力扣上有什么不会的就来看看大佬的。