Hard
题目描述
推箱子是一个游戏，玩家在仓库中推动箱子，试图将它们推到目标位置。
游戏由一个 m x n 的字符网格 grid 表示，其中每个元素都是墙、地板或箱子。
你的任务是根据以下规则将箱子 'B' 移动到目标位置 'T'：
- 字符
'S'表示玩家。如果是地板（空单元格），玩家可以在网格中向上、向下、向左、向右移动。 - 字符
'.'表示地板，意味着可以行走的空单元格。 - 字符
'#'表示墙，意味着障碍物（不可能在那里行走）。 - 网格中只有一个箱子
'B'和一个目标单元格'T'。 - 箱子可以通过站在箱子旁边然后朝箱子方向移动来推动到相邻的空单元格。这算作一次推动。
- 玩家不能穿过箱子。
返回将箱子推到目标位置的最小推动次数。如果无法到达目标位置，返回 -1。
示例 1：
输入：grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#",".","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
输出：3
解释：我们只返回箱子被推动的次数。
示例 2：
输入：grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#","#","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
输出：-1
示例 3：
输入：grid = [["#","#","#","#","#","#"],
["#","T",".",".","#","#"],
["#",".","#","B",".","#"],
["#",".",".",".",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
输出：5
解释：将箱子向下、左、左、上、上推动。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 20grid只包含字符'.'、'#'、'S'、'T'或'B'。- 网格中只有一个字符
'S'、'B'和'T'。
解题思路
这是一个复杂的BFS搜索问题，关键在于状态表示和状态转移。
核心思路
我们需要同时跟踪玩家位置和箱子位置，因为推动箱子需要玩家站在特定位置。状态可以表示为 (玩家行, 玩家列, 箱子行, 箱子列)。
解法分析
主要解法：双层BFS
- 外层BFS：枚举箱子的所有可能移动方向
- 内层BFS：检查玩家是否能到达推动箱子所需的位置
状态转移过程：
- 对于当前状态
(px, py, bx, by)，尝试将箱子推向四个方向 - 要将箱子从
(bx, by)推到(nbx, nby)，玩家需要站在箱子的对面位置(pbx, pby) - 使用内层BFS检查玩家是否能从当前位置
(px, py)到达(pbx, pby) - 如果可以到达，将新状态
(bx, by, nbx, nby)加入队列
优化要点：
- 使用
set记录访问过的状态，避免重复搜索 - 内层BFS只需要判断可达性，不需要记录路径长度
- 边界检查和障碍物检查要准确
时间复杂度： 外层状态数最多为 O(m²n²)，每个状态的内层BFS为 O(mn)，总体为 O(m³n³) 空间复杂度： O(m²n²) 用于存储访问状态
代码实现
class Solution {
public:
int minPushBox(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
int sx, sy, bx, by, tx, ty;
// 找到玩家、箱子、目标位置
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'S') {
sx = i; sy = j;
} else if (grid[i][j] == 'B') {
bx = i; by = j;
} else if (grid[i][j] == 'T') {
tx = i; ty = j;
}
}
}
int dirs[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
// 检查玩家是否能从(px,py)到达(targetX,targetY)，箱子在(bx,by)
auto canReach = [&](int px, int py, int targetX, int targetY, int bx, int by) -> bool {
if (px == targetX && py == targetY) return true;
vector<vector<bool>> visited(m, vector<bool>(n, false));
queue<pair<int,int>> q;
q.push({px, py});
visited[px][py] = true;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (auto& dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
!visited[nx][ny] && grid[nx][ny] != '#' &&
!(nx == bx && ny == by)) {
if (nx == targetX && ny == targetY) return true;
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
return false;
};
// BFS找最小推动次数
queue<tuple<int,int,int,int,int>> q; // px,py,bx,by,pushes
set<tuple<int,int,int,int>> visited;
q.push({sx, sy, bx, by, 0});
visited.insert({sx, sy, bx, by});
while (!q.empty()) {
auto [px, py, bx, by, pushes] = q.front();
q.pop();
if (bx == tx && by == ty) return pushes;
// 尝试推动箱子到四个方向
for (auto& dir : dirs) {
int nbx = bx + dir[0], nby = by + dir[1]; // 箱子新位置
int pbx = bx - dir[0], pby = by - dir[1]; // 玩家需要站的位置
// 检查箱子新位置是否有效
if (nbx < 0 || nbx >= m || nby < 0 || nby >= n || grid[nbx][nby] == '#')
continue;
// 检查玩家需要站的位置是否有效
if (pbx < 0 || pbx >= m || pby < 0 || pby >= n || grid[pbx][pby] == '#')
continue;
// 检查这个状态是否已访问
if (visited.count({bx, by, nbx, nby})) continue;
// 检查玩家是否能到达推箱子的位置
if (canReach(px, py, pbx, pby, bx, by)) {
visited.insert({bx, by, nbx, nby});
q.push({bx, by, nbx, nby, pushes + 1});
}
}
}
return -1;
}
};
class Solution:
def minPushBox(self, grid: List[List[str]]) -> int:
from collections import deque
m, n = len(grid), len(grid[0])
# 找到玩家、箱子、目标位置
for i in range(m):
for j in range(n):
if grid[i][j] == 'S':
sx, sy = i, j
elif grid[i][j] == 'B':
bx, by = i, j
elif grid[i][j] == 'T':
tx, ty = i, j
dirs = [(0,1), (0,-1), (1,0), (-1,0)]
def canReach(px, py, targetX, targetY, bx, by):
"""检查玩家是否能从(px,py)到达(targetX,targetY)，箱子在(bx,by)"""
if px == targetX and py == targetY:
return True
visited = [[False] * n for _ in range(m)]
queue = deque([(px, py)])
visited[px][py] = True
while queue:
x, y = queue.popleft()
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if (0 <= nx < m and 0 <= ny < n and
not visited[nx][ny] and grid[nx][ny] != '#' and
not (nx == bx and ny == by)):
if nx == targetX and ny == targetY:
return True
visited[nx][ny] = True
queue.append((nx, ny))
return False
# BFS找最小推动次数
queue = deque([(sx, sy, bx, by, 0)]) # px, py, bx, by, pushes
visited = {(sx, sy, bx, by)}
while queue:
px, py, bx, by, pushes = queue.popleft()
if bx == tx and by == ty:
return pushes
# 尝试推动箱子到四个方向
for dx, dy in dirs:
nbx, nby = bx + dx, by + dy # 箱子新位置
pbx, pby = bx - dx, by - dy # 玩家需要站的位置
# 检查箱子新位置是否有效
if not (0 <= nbx < m and 0 <= nby < n) or grid[nbx][nby] == '#':
continue
# 检查玩家需要站的位置是否有效
if not (0 <= pbx < m and 0 <= pby < n) or grid[pbx][pby] == '#':
continue
# 检查这个状态是否已访问
if (bx, by, nbx, nby) in visited:
continue
# 检查玩家是否能到达推箱子的位置
if canReach(px, py, pbx, pby, bx, by):
visited.add((bx, by, nbx, nby))
queue.append((bx, by, nbx, nby, pushes + 1))
return -1
public class Solution {
public int MinPushBox(char[][] grid) {
int m = grid.Length, n = grid[0].Length;
int sx = 0, sy = 0, bx = 0, by = 0, tx = 0, ty = 0;
// 找到玩家、箱子、目标位置
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'S') {
sx = i; sy = j;
} else if (grid[i][j] == 'B') {
bx = i; by = j;
} else if (grid[i][j] == 'T') {
tx = i; ty = j;
}
}
}
int[][] dirs = new int[][] { new int[]{0,1}, new int[]{0,-1}, new int[]{1,0}, new int[]{-1,0} };
bool CanReach(int px, int py, int targetX, int targetY, int bx, int by) {
if (px == targetX && py == targetY) return true;
bool[,] visited = new bool[m, n];
Queue<(int, int)> queue = new Queue<(int, int)>();
queue.Enqueue((px, py));
visited[px, py] = true;
while (queue.Count > 0) {
var (x, y) = queue.Dequeue();
foreach (var dir in dirs) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
!visited[nx, ny] && grid[nx][ny] != '#' &&
!(nx == bx && ny == by)) {
if (nx == targetX && ny == targetY) return true;
visited[nx, ny] = true;
queue.Enqueue((nx, ny));
}
}
}
return false;
}
// BFS找最小推动次数
Queue<(int, int, int, int, int)> queue = new Queue<(int, int, int, int, int)>();
HashSet<(int, int, int, int)> visited = new HashSet<(int, int, int, int)>();
queue.Enqueue((sx, sy, bx, by, 0));
visited.Add((sx, sy, bx, by));
while (queue.Count > 0) {
var (px, py, bx, by, pushes) = queue.Dequeue();
if (bx == tx && by == ty) return pushes;
// 尝试推动箱子到四个方向
foreach (var dir in dirs) {
int nbx = bx + dir[0], nby = by + dir[1]; // 箱子新位置
int pbx = bx - dir[0], pby = by - dir[1]; // 玩家需要站的位置
// 检查箱子新位置是否有效
if (nbx < 0 || nbx >= m || nby < 0 || nby >= n || grid[nbx][nby] == '#')
continue;
// 检查玩家需要站的位置是否有效
if (pbx < 0 || pbx >= m || pby < 0 || pby >= n || grid[pbx][pby] == '#')
continue;
// 检查这个状态是否已访问
if (visited.Contains((bx, by, nbx, nby))) continue;
// 检查玩家是否能到达推箱子的位置
if (CanReach(px, py, pbx, pby, bx, by)) {
visited.Add((bx, by, nbx, nby));
queue.Enqueue((bx, by, nbx, nby, pushes + 1));
}
}
}
return -1;
}
}
var minPushBox = function(grid) {
const m = grid.length, n = grid[0].length;
let boxR, boxC, playerR, playerC, targetR, targetC;
// Find initial positions
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 'B') {
boxR = i; boxC = j;
} else if (grid[i][j] === 'S') {
playerR = i; playerC = j;
} else if (grid[i][j] === 'T') {
targetR = i; targetC = j;
}
}
}
const dirs = [[-1,0], [1,0], [0,-1], [0,1]];
// Check if player can reach a position without going through the box
const canPlayerReach = (fromR, fromC, toR, toC, boxR, boxC) => {
if (fromR === toR && fromC === toC) return true;
const visited = new Set();
const queue = [[fromR, fromC]];
visited.add(`${fromR},${fromC}`);
while (queue.length) {
const [r, c] = queue.shift();
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
grid[nr][nc] !== '#' &&
!(nr === boxR && nc === boxC) &&
!visited.has(`${nr},${nc}`)) {
if (nr === toR && nc === toC) return true;
visited.add(`${nr},${nc}`);
queue.push([nr, nc]);
}
}
}
return false;
};
const queue = [[boxR, boxC, playerR, playerC, 0]];
const visited = new Set();
visited.add(`${boxR},${boxC},${playerR},${playerC}`);
while (queue.length) {
const [bR, bC, pR, pC, pushes] = queue.shift();
if (bR === targetR && bC === targetC) {
return pushes;
}
// Try pushing box in each direction
for (const [dr, dc] of dirs) {
const newBoxR = bR + dr, newBoxC = bC + dc;
const pushFromR = bR - dr, pushFromC = bC - dc;
// Check if new box position is valid
if (newBoxR < 0 || newBoxR >= m || newBoxC < 0 || newBoxC >= n ||
grid[newBoxR][newBoxC] === '#') continue;
// Check if push position is valid
if (pushFromR < 0 || pushFromR >= m || pushFromC < 0 || pushFromC >= n ||
grid[pushFromR][pushFromC] === '#') continue;
// Check if player can reach the push position
if (!canPlayerReach(pR, pC, pushFromR, pushFromC, bR, bC)) continue;
const state = `${newBoxR},${newBoxC},${bR},${bC}`;
if (!visited.has(state)) {
visited.add(state);
queue.push([newBoxR, newBoxC, bR, bC, pushes + 1]);
}
}
}
return -1;
};
复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(m³n³) | 外层状态数O(m²n²)，每个状态内层BFS为O(mn) |
| 空间复杂度 | O(m²n²) | 存储访问状态的哈希表空间 |