目标
给你一个 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'。
学生通过 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'。
学生通过 3 次移动收集了所有垃圾。因此，输出是 3。示例 3：
输入: classroom = ["L.S", "RXL"], energy = 3
输出: -1
解释:
没有有效路径可以收集所有 'L'。说明：
- 1 <= m == classroom.length <= 20
- 1 <= n == classroom[i].length <= 20
- classroom[i][j] 是 'S'、'L'、'R'、'X' 或 '.' 之一
- 1 <= energy <= 50
- 网格图中恰好有 一个 'S'。
- 网格图中 最多 有 10 个 'L' 单元格。
思路
学生从起点出发清理教室的垃圾，初始能量为 energy，向上下左右四个方向移动需要消耗 1 能量。教室里有障碍物，学生不能移动到障碍物的格子。能量重置点可以恢复能量到初始值。返回从起点出发清理所有垃圾所需的最少移动。
考虑使用 BFS，维护状态 (x, y, e, mask)，使用四维数组维护是否处理过。
代码
/**
* @date 2026-09-01 9:38
*/
public class MinMoves3568 {
public int minMoves(String[] classroom, int energy) {
int sx = -1, sy = -1;
int m = classroom.length;
int n = classroom[0].length();
int[][] directions = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int[][] grid = new int[m][n];
int no = 1;
int all = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
char c = classroom[i].charAt(j);
if (c == 'S') {
sy = j;
sx = i;
} else if (c == 'L') {
all |= 1 << no;
grid[i][j] = no++;
} else if (c == 'X') {
grid[i][j] = -1;
} else if (c == 'R') {
grid[i][j] = -2;
}
}
}
boolean[][][][] visited = new boolean[m][n][energy + 1][all + 1];
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[]{sx, sy, energy, 0});
int res = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int[] p = q.poll();
if (visited[p[0]][p[1]][p[2]][p[3]]) {
continue;
}
visited[p[0]][p[1]][p[2]][p[3]] = true;
if (p[3] == all) {
return res;
}
if (p[2] == 0) {
continue;
}
for (int[] d : directions) {
int nx = p[0] + d[0];
int ny = p[1] + d[1];
int e = p[2];
int mask = p[3];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] != -1) {
if (grid[nx][ny] > 0) {
e--;
mask |= 1 << grid[nx][ny];
} else if (grid[nx][ny] == -2) {
e = energy;
} else {
e--;
}
if (!visited[nx][ny][e][mask]) {
q.offer(new int[]{nx, ny, e, mask});
}
}
}
}
res++;
}
return -1;
}
}
性能
