2025-11-17：清理教室的最少移动。用go语言，给出一个 m×n 的格子地图 classroom，地图上的每个格子可能是以下几类字符之一：

• 起点 S：学生的出发位置；

• 垃圾 L：需要被收集，捡起后该格变为普通空格；

• 补能点 R：站在该格会把当前能量恢复到最大值（可以多次使用）；

• 障碍 X：不可通行的格子；

• 空地 .：普通可走的格子。

同时给定一个整数 energy，表示学生的最大能量值。学生从 S 出发，初始能量为 energy。每向上下左右相邻移动一步都会消耗 1 点能量。若能量为 0，则无法继续移动，除非此时所在格子为补能点 R（此时能量会被恢复到满），然后才能继续行走。补能点可以被反复利用。目标是把地图上所有的垃圾 L 全部捡完。

要求返回收集完所有垃圾所需的最少步数；如果无法完成，则返回 -1。

1 <= m == classroom.length <= 20。

1 <= n == classroom[i].length <= 20。

classroom[i][j] 是 ‘S’、‘L’、‘R’、‘X’ 或 ‘.’ 之一。

1 <= energy <= 50。

网格图中恰好有 一个 ‘S’。

网格图中 最多 有 10 个 ‘L’ 单元格。

输入: 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。

题目来自力扣3568。

解决过程分步描述

1. 初始化与网格扫描

   • 代码首先读取网格的行数m和列数n，并初始化一个二维数组idx，其大小与网格相同，用于标记垃圾位置。
   • 遍历网格中的每个单元格：
     • 统计垃圾L的数量cntL，并为每个垃圾位置分配一个唯一的位掩码（例如，第一个垃圾对应1 << 0，第二个对应1 << 1），存储在idx中。位掩码用于后续状态压缩，表示垃圾的收集状态。
     • 记录起点S的坐标(sx, sy)作为搜索的起始点。
   • 定义四个移动方向：上、下、左、右。

2. 状态记录结构设置

   • 创建一个三维数组maxEnergy，维度为m × n × (1 << cntL)。其中：
     • 前两个维度表示网格中的位置(x, y)。
     • 第三个维度是状态掩码（位掩码），长度为u = 1 << cntL，用于表示哪些垃圾已被收集（例如，掩码011表示前两个垃圾已收集）。
   • maxEnergy[x][y][mask]存储在位置(x, y)且收集状态为mask时，学生剩余的最大能量。初始值设为-1，表示该状态未被访问过。
   • 初始化起点状态：maxEnergy[sx][sy][0] = energy（起点，未收集任何垃圾，能量满）。

3. BFS（广度优先搜索）准备

   • 使用队列（具体为切片）进行BFS，队列中的每个元素是一个元组(x, y, e, mask)，表示当前位置、剩余能量、垃圾收集状态。
   • 初始状态(sx, sy, energy, 0)入队，表示从起点开始，能量满，未收集垃圾。
   • 设置步数计数器ans（初始为0），BFS按层遍历，每处理一层代表学生移动一步。

4. BFS核心循环

   • 循环直到队列为空：
     • 记录当前层的所有状态（tmp队列），然后清空主队列以准备下一层。
     • 对于当前层的每个状态(x, y, e, mask)：
       • 目标检查：如果mask == u-1（即所有垃圾位被置1，表示全部收集完成），立即返回当前步数ans作为答案。
       • 能量检查：如果剩余能量e == 0，跳过该状态（无法移动，除非在补能点，但移动决策在下一步处理）。
       • 尝试移动：遍历四个方向（上、下、左、右），计算新位置(nx, ny)：
         • 检查新位置是否在网格内且不是障碍物X。若无效，跳过。
         • 能量更新：
           • 通常情况：移动消耗1点能量，新能量newE = e - 1。
           • 特殊规则：如果新位置是补能点R，则能量恢复为最大值energy（即newE = energy）。
         • 垃圾收集更新：如果新位置有垃圾L，更新状态掩码newMask = mask | idx[nx][ny]（通过位操作标记该垃圾已收集）；否则newMask = mask。
       • 状态更新条件：比较新能量newE与maxEnergy[nx][ny][newMask]：
         • 如果newE > maxEnergy[nx][ny][newMask]，说明新路径在该状态下能量更高（更有利，因为能量高意味着移动潜力大），则更新maxEnergy值为newE，并将新状态(nx, ny, newE, newMask)加入下一层队列。
         • 否则，忽略该状态（避免重复或更差路径）。
     • 当前层处理完成后，步数ans加1，开始处理下一层。

5. 终止与返回

   • 如果B队列为空仍未找到目标状态（即所有垃圾未被收集），返回-1表示无法完成。
   • 如果找到目标状态，返回步数ans。

关键设计要点

• 状态压缩：使用位掩码mask表示垃圾收集状态，将最多10个垃圾的收集情况压缩为一个整数，减少状态数。
• 能量优先策略：maxEnergy数组记录每个位置和状态下的最大剩余能量。这确保优先探索能量更高的路径（能量高意味着移动能力更强），避免重复访问较差状态。
• BFS层序遍历：每层对应一步移动，保证第一次到达目标状态时的步数是最少的。
• 补能点处理：在移动至R格时立即恢复能量，而非在移动前判断，符合问题规则。

时间复杂度和空间复杂度

• 时间复杂度：O(m × n × 2^L × 4)，其中：
  • m和n是网格的尺寸（最大20），L是垃圾数量（最多10）。
  • 状态总数为O(m × n × 2^L)，每个状态最多尝试4个方向。
  • 代入最大值：20 × 20 × 2¹⁰ × 4 ≈ 1.6 × 10⁶，在合理范围内。
• 空间复杂度：O(m × n × 2^L)，主要用于存储maxEnergy三维数组。代入最大值：20 × 20 × 1024 ≈ 409,600个元素（每个元素为int8，占用约400KB）。

该方法通过BFS与状态压缩的结合，高效地解决了垃圾收集问题，确保在能量约束下找到最短路径。

Go完整代码如下：

package main

import (
	"fmt"
)

func minMoves(classroom []string, energy int) (ans int) {
	m, n := len(classroom), len(classroom[0])
	idx := make([][]int, m)
	for i := range idx {
		idx[i] = make([]int, n)
	}
	var cntL, sx, sy int
	for i, row := range classroom {
		for j, b := range row {
			if b == 'L' {
				idx[i][j] = 1 << cntL
				cntL++
			} else if b == 'S' {
				sx, sy = i, j
			}
		}
	}

	dirs := []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
	u := 1 << cntL
	maxEnergy := make([][][]int8, m)
	for i := range maxEnergy {
		maxEnergy[i] = make([][]int8, n)
		for j := range maxEnergy[i] {
			maxEnergy[i][j] = make([]int8, u)
			for k := range maxEnergy[i][j] {
				maxEnergy[i][j][k] = -1
			}
		}
	}

	maxEnergy[sx][sy][0] = int8(energy)
	type tuple struct{ x, y, e, mask int }
	q := []tuple{{sx, sy, energy, 0}}

	for ; len(q) > 0; ans++ {
		tmp := q
		q = nil
		for _, p := range tmp {
			if p.mask == u-1 {
				return
			}
			if p.e == 0 {
				continue
			}
			for _, d := range dirs {
				x, y := p.x+d.x, p.y+d.y
				if 0 <= x && x < m && 0 <= y && y < n && classroom[x][y] != 'X' {
					newE := p.e - 1
					if classroom[x][y] == 'R' {
						newE = energy
					}
					newMask := p.mask | idx[x][y]
					if int8(newE) > maxEnergy[x][y][newMask] {
						maxEnergy[x][y][newMask] = int8(newE)
						q = append(q, tuple{x, y, newE, newMask})
					}
				}
			}
		}
	}
	return -1
}

func main() {
	classroom := []string{"S.", "XL"}
	energy := 2
	result := minMoves(classroom, energy)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List
from collections import deque

def minMoves(classroom: List[str], energy: int) -> int:
    m, n = len(classroom), len(classroom[0])
    idx = [[0] * n for _ in range(m)]
    cntL = 0
    sx, sy = 0, 0
    
    # 预处理地图，标记钥匙和起点
    for i in range(m):
        for j in range(n):
            if classroom[i][j] == 'L':
                idx[i][j] = 1 << cntL
                cntL += 1
            elif classroom[i][j] == 'S':
                sx, sy = i, j
    
    # 方向数组
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    u = 1 << cntL  # 所有钥匙收集完成的状态
    
    # 三维数组，记录每个位置和状态下的最大能量值
    maxEnergy = [[[-1] * u for _ in range(n)] for _ in range(m)]
    maxEnergy[sx][sy][0] = energy
    
    # 使用队列进行BFS
    q = deque()
    q.append((sx, sy, energy, 0))
    ans = 0
    
    while q:
        # 按层遍历
        for _ in range(len(q)):
            x, y, e, mask = q.popleft()
            
            # 如果收集了所有钥匙，返回当前步数
            if mask == u - 1:
                return ans
            
            # 如果能量为0，无法移动
            if e == 0:
                continue
                
            # 尝试四个方向
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                
                # 检查边界和障碍物
                if 0 <= nx < m and 0 <= ny < n and classroom[nx][ny] != 'X':
                    new_e = e - 1  # 默认消耗1点能量
                    
                    # 如果是能量恢复点，恢复能量
                    if classroom[nx][ny] == 'R':
                        new_e = energy
                    
                    # 更新钥匙状态
                    new_mask = mask | idx[nx][ny]
                    
                    # 如果新状态的能量比之前记录的大，更新并加入队列
                    if new_e > maxEnergy[nx][ny][new_mask]:
                        maxEnergy[nx][ny][new_mask] = new_e
                        q.append((nx, ny, new_e, new_mask))
        
        ans += 1
    
    return -1

def main():
    classroom = ["S.", "XL"]
    energy = 2
    result = minMoves(classroom, energy)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>
#include <cstdint>
using namespace std;

int minMoves(vector<string>& classroom, int energy) {
    int m = classroom.size(), n = classroom[0].size();
    vector<vector<int>> idx(m, vector<int>(n, 0));
    int cntL = 0, sx = 0, sy = 0;

    // 预处理地图，标记钥匙和起点
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (classroom[i][j] == 'L') {
                idx[i][j] = 1 << cntL;
                cntL++;
            } else if (classroom[i][j] == 'S') {
                sx = i;
                sy = j;
            }
        }
    }

    // 方向数组
    vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int u = 1 << cntL;  // 所有钥匙收集完成的状态

    // 三维数组，记录每个位置和状态下的最大能量值
    vector<vector<vector<int8_t>>> maxEnergy(m,
                                             vector<vector<int8_t>>(n,
                                                                    vector<int8_t>(u, -1)));

    maxEnergy[sx][sy][0] = energy;

    // 使用队列进行BFS
    using Tuple = tuple<int, int, int, int>;
    queue<Tuple> q;
    q.push({sx, sy, energy, 0});
    int ans = 0;

    while (!q.empty()) {
        int size = q.size();

        // 按层遍历
        for (int i = 0; i < size; i++) {
            auto [x, y, e, mask] = q.front();
            q.pop();

            // 如果收集了所有钥匙，返回当前步数
            if (mask == u - 1) {
                return ans;
            }

            // 如果能量为0，无法移动
            if (e == 0) {
                continue;
            }

            // 尝试四个方向
            for (auto [dx, dy] : dirs) {
                int nx = x + dx;
                int ny = y + dy;

                // 检查边界和障碍物
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && classroom[nx][ny] != 'X') {
                    int new_e = e - 1;  // 默认消耗1点能量

                    // 如果是能量恢复点，恢复能量
                    if (classroom[nx][ny] == 'R') {
                        new_e = energy;
                    }

                    // 更新钥匙状态
                    int new_mask = mask | idx[nx][ny];

                    // 如果新状态的能量比之前记录的大，更新并加入队列
                    if (new_e > maxEnergy[nx][ny][new_mask]) {
                        maxEnergy[nx][ny][new_mask] = new_e;
                        q.push({nx, ny, new_e, new_mask});
                    }
                }
            }
        }
        ans++;
    }

    return -1;
}

int main() {
    vector<string> classroom = {"S.", "XL"};
    int energy = 2;
    int result = minMoves(classroom, energy);
    cout << result << endl;
    return 0;
}