Medium
题目描述
给你一个 m x n 的网格 classroom，其中一名学生志愿者负责清理散落在房间里的垃圾。网格中的每个单元格是以下之一：
'S'：学生的起始位置'L'：必须收集的垃圾（收集后，该单元格变为空）'R'：重置区域，将学生的能量恢复到满容量，无论当前能量水平如何（可以多次使用）'X'：学生无法通过的障碍物'.'：空白空间
还给你一个整数 energy，表示学生的最大能量容量。学生从起始位置 'S' 开始，拥有这个能量值。
每次移动到相邻单元格（上、下、左、右）消耗 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'。
学生用 2 次移动收集了所有垃圾。因此输出是 2。
示例 2：
输入：classroom = ["LS", "RL"], energy = 4
输出：3
示例 3：
输入：classroom = ["L.S", "RXL"], energy = 3
输出：-1
约束条件：
1 <= m == classroom.length <= 201 <= n == classroom[i].length <= 20classroom[i][j]是'S','L','R','X', 或'.'之一1 <= energy <= 50- 网格中恰好有一个
'S' - 网格中最多有 10 个
'L'单元格
解题思路
这是一个状态空间搜索问题，需要使用 BFS 来找到最短路径。关键在于正确建模状态。
核心思路：
状态定义：每个状态包含
(x, y, mask, energy)，其中：(x, y)是当前位置mask是位掩码，表示已收集的垃圾（第i个垃圾对应第i位）energy是当前剩余能量
BFS搜索：从起始位置开始，每次尝试四个方向的移动：
- 检查是否越界或遇到障碍物
- 更新能量（每移动一步消耗1能量）
- 如果到达垃圾位置，更新mask
- 如果到达重置区域，恢复满能量
- 如果能量不足且不在重置区域，跳过该状态
剪枝优化：使用三维数组记录每个位置和mask组合下见过的最大能量值，如果当前状态的能量不超过之前记录的值，则跳过（因为更少的能量不可能产生更优解）。
终止条件：当mask等于所有垃圾都被收集的完整mask时，返回步数。
时间复杂度：O(m × n × 2^L × energy)，其中L是垃圾数量（最多10个）。 空间复杂度：O(m × n × 2^L × energy) 用于状态记录。
代码实现
class Solution {
public:
int minMoves(vector<string>& classroom, int energy) {
int m = classroom.size(), n = classroom[0].size();
int sx = -1, sy = -1;
vector<pair<int, int>> litters;
// Find start position and litter positions
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (classroom[i][j] == 'S') {
sx = i; sy = j;
} else if (classroom[i][j] == 'L') {
litters.push_back({i, j});
}
}
}
int L = litters.size();
int fullMask = (1 << L) - 1;
// BFS with state (x, y, mask, energy, steps)
queue<tuple<int, int, int, int, int>> q;
vector<vector<vector<int>>> bestEnergy(m, vector<vector<int>>(n, vector<int>(1 << L, -1)));
q.push({sx, sy, 0, energy, 0});
bestEnergy[sx][sy][0] = energy;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
while (!q.empty()) {
auto [x, y, mask, e, steps] = q.front();
q.pop();
if (mask == fullMask) {
return steps;
}
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx < 0 || nx >= m || ny < 0 || ny >= n || classroom[nx][ny] == 'X') {
continue;
}
int newE = e - 1;
int newMask = mask;
// Check if we're at a litter position
for (int i = 0; i < L; i++) {
if (litters[i].first == nx && litters[i].second == ny) {
newMask |= (1 << i);
break;
}
}
// Check if we're at a reset area
if (classroom[nx][ny] == 'R') {
newE = energy;
}
// If energy is insufficient and not at reset area, skip
if (newE < 0) {
continue;
}
// Pruning: skip if we've seen better energy for this state
if (bestEnergy[nx][ny][newMask] >= newE) {
continue;
}
bestEnergy[nx][ny][newMask] = newE;
q.push({nx, ny, newMask, newE, steps + 1});
}
}
return -1;
}
};
class Solution:
def minMoves(self, classroom: List[str], energy: int) -> int:
from collections import deque
m, n = len(classroom), len(classroom[0])
sx = sy = -1
litters = []
# Find start position and litter positions
for i in range(m):
for j in range(n):
if classroom[i][j] == 'S':
sx, sy = i, j
elif classroom[i][j] == 'L':
litters.append((i, j))
L = len(litters)
full_mask = (1 << L) - 1
# BFS with state (x, y, mask, energy, steps)
queue = deque([(sx, sy, 0, energy, 0)])
best_energy = {}
best_energy[(sx, sy, 0)] = energy
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while queue:
x, y, mask, e, steps = queue.popleft()
if mask == full_mask:
return steps
for dx, dy in directions:
nx, ny = x + dx, y + dy
if nx < 0 or nx >= m or ny < 0 or ny >= n or classroom[nx][ny] == 'X':
continue
new_e = e - 1
new_mask = mask
# Check if we're at a litter position
for i, (lx, ly) in enumerate(litters):
if lx == nx and ly == ny:
new_mask |= (1 << i)
break
# Check if we're at a reset area
if classroom[nx][ny] == 'R':
new_e = energy
# If energy is insufficient, skip
if new_e < 0:
continue
# Pruning: skip if we've seen better energy for this state
state_key = (nx, ny, new_mask)
if state_key in best_energy and best_energy[state_key] >= new_e:
continue
best_energy[state_key] = new_e
queue.append((nx, ny, new_mask, new_e, steps + 1))
return -1
public class Solution {
public int MinMoves(string[] classroom, int energy) {
int m = classroom.Length, n = classroom[0].Length;
int sx = -1, sy = -1;
var litters = new List<(int, int)>();
// Find start position and litter positions
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (classroom[i][j] == 'S') {
sx = i; sy = j;
} else if (classroom[i][j] == 'L') {
litters.Add((i, j));
}
}
}
int L = litters.Count;
int fullMask = (1 << L) - 1;
// BFS with state (x, y, mask, energy, steps)
var queue = new Queue<(int x, int y, int mask, int energy, int steps)>();
var bestEnergy = new Dictionary<(int, int, int), int>();
queue.Enqueue((sx, sy, 0, energy, 0));
bestEnergy[(sx, sy, 0)] = energy;
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
while (queue.Count > 0) {
var (x, y, mask, e, steps) = queue.Dequeue();
if (mask == fullMask) {
return steps;
}
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx < 0 || nx >= m || ny < 0 || ny >= n || classroom[nx][ny] == 'X') {
continue;
}
int newE = e - 1;
int newMask = mask;
// Check if we're at a litter position
for (int i = 0; i < L; i++) {
if (litters[i].Item1 == nx && litters[i].Item2 == ny) {
newMask |= (1 << i);
break;
}
}
// Check if we're at a reset area
if (classroom[nx][ny] == 'R') {
newE = energy;
}
// If energy is insufficient, skip
if (newE < 0) {
continue;
}
// Pruning: skip if we've seen better energy for this state
var stateKey = (nx, ny, newMask);
if (bestEnergy.ContainsKey(stateKey) && bestEnergy[stateKey] >= newE) {
continue;
}
bestEnergy[stateKey] = newE;
queue.Enqueue((nx, ny, newMask, newE, steps + 1));
}
}
return -1;
}
}
var minMoves = function(classroom, energy) {
const m = classroom.length;
const n = classroom[0].length;
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
let start = null;
const litters = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (classroom[i][j] === 'S') {
start = [i, j];
} else if (classroom[i][j] === 'L') {
litters.push([i, j]);
}
}
}
const numLitters = litters.length;
if (numLitters === 0) return 0;
// BFS to find shortest path between any two points with energy constraint
function bfs(from, to, maxEnergy) {
const queue = [[from[0], from[1], maxEnergy, 0]];
const visited = new Set();
while (queue.length > 0) {
const [x, y, currentEnergy, moves] = queue.shift();
if (x === to[0] && y === to[1]) {
return moves;
}
const state = `${x},${y},${currentEnergy}`;
if (visited.has(state)) continue;
visited.add(state);
for (const [dx, dy] of directions) {
const nx = x + dx;
const ny = y + dy;
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (classroom[nx][ny] === 'X') continue;
let newEnergy = currentEnergy - 1;
if (newEnergy < 0) continue;
if (classroom[nx][ny] === 'R') {
newEnergy = maxEnergy;
}
queue.push([nx, ny, newEnergy, moves + 1]);
}
}
return -1;
}
// DP with bitmask for collected litters
const memo = new Map();
function dp(pos, mask, currentEnergy) {
if (mask === (1 << numLitters) - 1) {
return 0;
}
const state = `${pos[0]},${pos[1]},${mask},${currentEnergy}`;
if (memo.has(state)) {
return memo.get(state);
}
let result = Infinity;
for (let i = 0; i < numLitters; i++) {
if (mask & (1 << i)) continue;
const dist = bfs(pos, litters[i], Math.max(currentEnergy, energy));
if (dist === -1) continue;
let energyAfterMove = currentEnergy - dist;
if (energyAfterMove < 0) {
energyAfterMove = energy - dist;
}
if (energyAfterMove < 0) continue;
const subResult = dp(litters[i], mask | (1 << i), energyAfterMove);
if (subResult !== Infinity) {
result = Math.min(result, dist + subResult);
}
}
memo.set(state, result);
return result;
}
const answer = dp(start, 0, energy);
return answer === Infinity ? -1 : answer;
};
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |