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+自定义哈希快不少