Leetcode每日一题 —— 3568. 清理教室的最少移动

写起来有点难受的一道题，虽然很明显能看出是 BFS，但尤其要注意其中几个状态的维护。

因为找的是收集所有垃圾所需的最小移动次数，且运动过程中有能量损耗，我们每个状态需要维护位置、剩余能量、已经收集的垃圾以及步数。

已经收集的垃圾这里如果我们每个状态都用表来存必定爆内存，但还好题目明确提出垃圾数量 <=10，可以用最多 10 个位来压缩存储状态。我们需要做的只是用一张表把每个垃圾映射到一个二进制位上，方便标记时进行位运算，所有位都为 1 时则垃圾收集完成。

还有一个很关键的点就是剪枝，这个看了提示才会过来，也就是 bestEnergy[newI][newJ][newMask]>=newE 这个判断。如果某个地方位置相同，收集的垃圾也相同，若之前有比当前剩余能量更大或相等的路径，则当前路径一定不会更优。

• 有没有可能剩的能量多的那条路径绕路更多，只是遇到了 R 呢？但其实 BFS 的性质决定了，如果之前已经有剩的能量多或相等的路径，那么其 step 数肯定 \le 当前这条路径的 step 数。所以才可以这样剪。```

struct State{
int i;
int j;
int energy;
int mask;
int step;
};

class Solution {
public:
int minMoves(vector<string>& classroom, int energy) {
int m=classroom.size(),n=classroom[0].size();
// 从 S 位置开始 BFS，最多有 10 个 L
int drcts[][2]={
{0,1},
{1,0},
{0,-1},
{-1,0},
};
// 可以预存垃圾的掩码
int gbMask[m][n];
memset(gbMask,0,sizeof(gbMask));
int gbCnt=0; // 垃圾数量
// S 所在的位置
int iPos,jPos;
// 先扫描网格
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(classroom[i][j]=='S'){
iPos=i;
jPos=j;
}else if(classroom[i][j]=='L'){
// 如果是 L 则记录
gbMask[i][j]=(1<<gbCnt);
gbCnt++;
}
}
}
// 一个垃圾都没有的话就不需要移动
if(gbCnt==0){
return 0;
}
// 收集所有垃圾后的完整掩码
int fullMask=(1<<gbCnt)-1;
// 标记每个位置，在收集了指定垃圾的情况下的最大能量
// 这里全部初始化为 -1，因为 0 也是可能会出现的值
vector<vector<vector<int>>> bestEnergy(m,vector<vector<int>>(n,vector<int>(1<<gbCnt,-1)));
// 注意收集了哪些垃圾也在状态里面
queue<State> q;
// 在开始位置，一个垃圾都还没收集的情况下是满能量的
bestEnergy[iPos][jPos][0]=energy;
q.emplace(State{iPos,jPos,energy,0,0});
while(!q.empty()){
int i=q.front().i, j=q.front().j, eLeft=q.front().energy, mask=q.front().mask, step=q.front().step;
q.pop();
// 如果所有垃圾已经收集完毕
if(mask==fullMask){
// 因为 BFS 本身保证首次遇到这个状态时步数是最少的，直接返回
return step;
}
if(eLeft==0){
// 没有能量了且当前位置不是 R，这个状态没法继续转移了
continue;
}
for(auto& d:drcts){
int newI=i+d[0],newJ=j+d[1];
if(newI>=0&&newI<m&&newJ>=0&&newJ<n&&classroom[newI][newJ]!='X'){
// 继续走一步需要耗费一个能量
int newE=eLeft-1;
int newMask=mask;
if(classroom[newI][newJ]=='L'){
newMask|=gbMask[newI][newJ];
}else if(classroom[newI][newJ]=='R'){
// 恢复能量
newE=energy;
}
// 剪枝: 相同位置且相同垃圾状态下，如果之前见过的最大能量 >= 当前位置能量，因为 BFS 的性质，当前状态肯定不会优于之前那个状态
if(bestEnergy[newI][newJ][newMask]>=newE){
continue;
}
// 否则当前能量肯定优于之前的
bestEnergy[newI][newJ][newMask]=newE;
q.emplace(State{
newI,
newJ,
newE,
newMask,
step+1,
});
}
}
}
// 无法收集完成
return -1;
}
};

Kotlin每日打卡（带状态记录的最短路径BFS）：```
class Solution {
companion object {
val DIRS = arrayOf(
intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0)
)
}

private data class Node(val x: Int, val y: Int, val energy: Int, val mask: Int)

fun minMoves(classroom: Array<String>, energy: Int): Int {
val m = classroom.size
val n = classroom[0].length
val maskIndex = Array(m) { IntArray(n) { 0 } }
var leftCount = 0
var startX = 0
var startY = 0
for (i in 0..<m) {
for (j in 0..<n) {
when (classroom[i][j]) {
'L' -> {
maskIndex[i][j] = 1 shl leftCount
leftCount++
}

'S' -> {
startX = i
startY = j
}
}
}
}

val maxStateCount = 1 shl leftCount
val targetMask = maxStateCount - 1
val visitedArr = Array(m) {
Array(n) {
Array(energy + 1) {
BooleanArray(maxStateCount) { false }
}
}
}

visitedArr[startX][startY][energy][0] = true

val queue = ArrayDeque<Node>()
queue.add(Node(startX, startY, energy, 0))

var ans = 0
while (queue.isNotEmpty()) {
val count = queue.size
for (i in 1..count) {
val node = queue.removeFirst()
if (node.mask == targetMask) {
return ans
}
if (node.energy == 0) {
continue
}
for ((dx, dy) in DIRS) {
val newX = node.x + dx
val newY = node.y + dy
if (newX in 0..<m && newY in 0..<n && classroom[newX][newY] != 'X') {
val newEnergy = if (classroom[newX][newY] == 'R') energy else node.energy - 1
val newMask = node.mask or maskIndex[newX][newY]
if (!visitedArr[newX][newY][newEnergy][newMask]) {
visitedArr[newX][newY][newEnergy][newMask] = true
queue.add(Node(newX, newY, newEnergy, newMask))
}
}
}
}

ans++
}
return -1
}
}

你这个状态压缩BFS思路没问题，不过 m*n 比较大的话光存坐标+状态就够吃内存了，建议用 unordered_map 的时候 key 拼成 long long（左32位坐标、右10位状态），比 pair+自定义哈希快不少