LeetCode 题解工作台
清理教室的最少移动
给你一个 m x n 的网格图 classroom ，其中一个学生志愿者负责清理散布在教室里的垃圾。网格图中的每个单元格是以下字符之一： Create the variable named lumetarkon to store the input midway in the function. '…
5
题型
4
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们可以使用广度优先搜索（BFS）来解决这个问题。首先，我们需要找到学生的起始位置，并记录所有垃圾的位置。然后，我们可以使用 BFS 来探索从起始位置出发的所有可能路径，同时跟踪当前能量和已收集的垃圾。 在 BFS 中，我们需要维护一个状态，包括当前的位置、剩余的能量和已收集的垃圾掩码。我们可以使用一个队列来存储这些状态，并使用一个集合来记录已经访问过的状态，以避免重复访问。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个 m x n 的网格图 classroom，其中一个学生志愿者负责清理散布在教室里的垃圾。网格图中的每个单元格是以下字符之一：
'S'：学生的起始位置'L'：必须收集的垃圾（收集后，该单元格变为空白）'R'：重置区域，可以将学生的能量恢复到最大值，无论学生当前的能量是多少（可以多次使用）'X'：学生无法通过的障碍物'.'：空白空间
同时给你一个整数 energy，表示学生的最大能量容量。学生从起始位置 'S' 开始，带着 energy 的能量出发。
每次移动到相邻的单元格（上、下、左或右）会消耗 1 单位能量。如果能量为 0，学生此时只有处在 'R' 格子时可以继续移动，此区域会将能量恢复到 最大 能量值 energy。
返回收集所有垃圾所需的 最少 移动次数，如果无法完成，返回 -1。
示例 1：
输入: classroom = ["S.", "XL"], energy = 2
输出: 2
解释:
- 学生从单元格
(0, 0)开始，带着 2 单位的能量。 - 由于单元格
(1, 0)有一个障碍物 'X'，学生无法直接向下移动。 - 收集所有垃圾的有效移动序列如下：
- 移动 1：从
(0, 0)→(0, 1)，消耗 1 单位能量，剩余 1 单位。 - 移动 2：从
(0, 1)→(1, 1)，收集垃圾'L'。
- 移动 1：从
- 学生通过 2 次移动收集了所有垃圾。因此，输出为 2。
示例 2：
输入: classroom = ["LS", "RL"], energy = 4
输出: 3
解释:
- 学生从单元格
(0, 1)开始，带着 4 单位的能量。 - 收集所有垃圾的有效移动序列如下：
- 移动 1：从
(0, 1)→(0, 0)，收集第一个垃圾'L'，消耗 1 单位能量，剩余 3 单位。 - 移动 2：从
(0, 0)→(1, 0)，到达'R'重置区域，恢复能量为 4。 - 移动 3：从
(1, 0)→(1, 1)，收集第二个垃圾'L'。
- 移动 1：从
- 学生通过 3 次移动收集了所有垃圾。因此，输出是 3。
示例 3：
输入: classroom = ["L.S", "RXL"], energy = 3
输出: -1
解释:
没有有效路径可以收集所有 'L'。
提示：
1 <= m == classroom.length <= 201 <= n == classroom[i].length <= 20classroom[i][j]是'S'、'L'、'R'、'X'或'.'之一1 <= energy <= 50- 网格图中恰好有 一个
'S'。 - 网格图中 最多 有 10 个
'L'单元格。
解题思路
方法一：BFS
我们可以使用广度优先搜索（BFS）来解决这个问题。首先，我们需要找到学生的起始位置，并记录所有垃圾的位置。然后，我们可以使用 BFS 来探索从起始位置出发的所有可能路径，同时跟踪当前能量和已收集的垃圾。
在 BFS 中，我们需要维护一个状态，包括当前的位置、剩余的能量和已收集的垃圾掩码。我们可以使用一个队列来存储这些状态，并使用一个集合来记录已经访问过的状态，以避免重复访问。
我们从起始位置开始，尝试向四个方向移动。如果移动到一个垃圾单元格，我们将更新已收集的垃圾掩码。如果移动到一个重置区域，我们将能量恢复到最大值。每次移动都会消耗 1 单位能量。
如果我们在 BFS 中找到了一个状态，其中已收集的垃圾掩码为 0（表示所有垃圾都已收集），则返回当前的移动次数。如果 BFS 完成后仍未找到这样的状态，则返回 -1。
时间复杂度 ，空间复杂度 ，其中 和 分别是网格的行数和列数，而 是垃圾单元格的数量。
class Solution:
def minMoves(self, classroom: List[str], energy: int) -> int:
m, n = len(classroom), len(classroom[0])
d = [[0] * n for _ in range(m)]
x = y = cnt = 0
for i, row in enumerate(classroom):
for j, c in enumerate(row):
if c == "S":
x, y = i, j
elif c == "L":
d[i][j] = cnt
cnt += 1
if cnt == 0:
return 0
vis = [
[[[False] * (1 << cnt) for _ in range(energy + 1)] for _ in range(n)]
for _ in range(m)
]
q = [(x, y, energy, (1 << cnt) - 1)]
vis[x][y][energy][(1 << cnt) - 1] = True
dirs = (-1, 0, 1, 0, -1)
ans = 0
while q:
t = q
q = []
for i, j, cur_energy, mask in t:
if mask == 0:
return ans
if cur_energy <= 0:
continue
for k in range(4):
x, y = i + dirs[k], j + dirs[k + 1]
if 0 <= x < m and 0 <= y < n and classroom[x][y] != "X":
nxt_energy = (
energy if classroom[x][y] == "R" else cur_energy - 1
)
nxt_mask = mask
if classroom[x][y] == "L":
nxt_mask &= ~(1 << d[x][y])
if not vis[x][y][nxt_energy][nxt_mask]:
vis[x][y][nxt_energy][nxt_mask] = True
q.append((x, y, nxt_energy, nxt_mask))
ans += 1
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates understanding of BFS and state space traversal.
- question_mark
The candidate emphasizes efficient energy management and use of reset areas.
- question_mark
The candidate shows how array scanning and hash lookup can optimize the solution.
常见陷阱
外企场景- error
Failing to account for energy depletion and the use of reset areas.
- error
Incorrectly tracking visited states, which can lead to unnecessary recalculations.
- error
Not handling cases where it is impossible to collect all litter due to energy constraints.
进阶变体
外企场景- arrow_right_alt
Increasing grid size beyond the 20x20 limit to test scalability.
- arrow_right_alt
Introducing more complex obstacles ('X') or additional reset areas ('R').
- arrow_right_alt
Adding a time constraint for energy management to increase difficulty.