M3568.清理教室的最少移动

bfs, bitmask, https://leetcode.cn/problems/minimum-moves-to-clean-the-classroom/

给你一个 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' 单元格。

为了避免「超时」，我们需要大幅剪枝那些「显然不可能更优」的状态。核心思路是：对于同一个位置、同一个垃圾收集掩码（mask），如果之前到达过并且当时剩余的能量 ≥ 这次到达的能量，那么后者就一定不会更优，也可以跳过。换句话说，只在「到达 (x,y) 且垃圾掩码为 mask 时，剩余能量 e 比之前任何一次到达同样状态时都要高」的情况下，才继续展开。

这样只需要一个三维数组 visited[x][y][mask] 来记录「在 (x,y)、已收集 mask 这组状态下，见过的最大剩余能量」。如果新到达的能量不超过这个值，就跳过。

主要优化点

状态定义
- x, y：当前位置
- mask：已收集的垃圾（用 0..(1<<L)-1 的比特掩码）
- e：当前剩余能量
剪枝逻辑
- 用 visited[x][y][mask] 存储「已到达 (x,y) 且垃圾掩码为 mask 时见过的最大剩余能量」。
- 当我们要把 (nx, ny, new_mask, ne) 入队时，如果 visited[nx][ny][new_mask] >= ne，说明之前到过同样 (nx,ny,new_mask) 的状态时，剩余能量就已经 ≥ 当前要入队的 ne，那么当前这条路径就“更差”了，可以直接剪掉。
- 反之，就把 visited[nx][ny][new_mask] = ne，并把新状态入队。
能量耗尽处理
- 出队时，如果 e == 0：
  - 只有当 classroom[x][y] == 'R'，才能把 e 重置成最大能量后再继续向四周走；否则「停在这里就动不了了」，直接 continue 跳过。
- 这样保证：真正「踏出一步」时一定是消耗 1 点能量后才移动。
复杂度剪枝效果
- 原来最坏可能有 $400 \times 2^{10} \times 51 \approx 20 \times 10^{6}$ 个（位置×掩码×能量）状态。而采用「只记录最大剩余能量」后，每个 $(x, y, m a s k)$ 最多只会以「增长的剩余能量」被访问若干次，实际大幅削减了重复遍历。对 20×20×10 的可行网格，BFS 全遍不会爆内存，也不会 TLE 了。

代码实现

python

from typing import List
from collections import deque

class Solution:
    def minMoves(self, classroom: List[str], energy: int) -> int:
        m, n = len(classroom), len(classroom[0])
        dirs = [(-1,0), (1,0), (0,-1), (0,1)]
        
        # 1. 先扫描出：起点 S、所有 L 的坐标并编号
        garbage = {}     # (i,j) -> idx
        start = None
        g_index = 0
        for i in range(m):
            for j in range(n):
                c = classroom[i][j]
                if c == 'S':
                    start = (i, j)
                elif c == 'L':
                    garbage[(i, j)] = g_index
                    g_index += 1
        
        total_garbage = g_index
        full_mask = (1 << total_garbage) - 1
        
        # 2. visited[x][y][mask] 记录：在 (x,y)、已收集 mask 时，"见过的最大剩余能量"
        #    初始化为 -1（表示还没到过或者能量都更低）
        visited = [
            [ [-1] * (1 << total_garbage) for _ in range(n) ]
            for _ in range(m)
        ]
        
        # 3. BFS 队列元素： (x, y, 剩余能量 e, collected_mask, steps)
        dq = deque()
        sx, sy = start
        visited[sx][sy][0] = energy
        dq.append((sx, sy, energy, 0, 0))
        
        while dq:
            x, y, e, mask, steps = dq.popleft()
            # 如果已经全收集，直接返回步数
            if mask == full_mask:
                return steps
            
            # 如果当前能量用光了：
            if e == 0:
                # 只有在 R 上才能把 e 重置，否则卡死
                if classroom[x][y] == 'R':
                    e = energy
                else:
                    continue
            
            # 4. 向四周扩展
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                # 边界 + 障碍 检查
                if not (0 <= nx < m and 0 <= ny < n): 
                    continue
                if classroom[nx][ny] == 'X':
                    continue
                
                # 走这一步前，e > 0，走一步消耗 1 能量
                ne = e - 1
                nmask = mask
                
                # 如果落在 L 上，那么把对应那一位打上去
                if (nx, ny) in garbage:
                    nmask |= (1 << garbage[(nx, ny)])
                
                # 如果落在 R 上，能量直接充满
                if classroom[nx][ny] == 'R':
                    ne = energy
                
                # 剪枝：如果我们已经在 (nx,ny,nmask) 见过 >= ne 的剩余能量，这条路就更劣，跳过
                if visited[nx][ny][nmask] >= ne:
                    continue
                
                # 否则更新为 ne，入队
                visited[nx][ny][nmask] = ne
                dq.append((nx, ny, ne, nmask, steps + 1))
        
        # BFS 结束，没有收集完所有 L
        return -1

在最坏情况下，visited[x][y][mask] 只会被更新有限次（每次都必须有更高的剩余能量才更新），大大剪枝了原本可能的 20M+ 状态
实际跑 m,n ≤ 20 时，BFS 很快能结束，不会超时。

M3568.清理教室的最少移动 ​

M3568.清理教室的最少移动