LeetCode 解題筆記：3568. Minimum Moves to Clean the Classroom

作者：王一哲
日期：2026年9月1日


LeetCode 題目連結：3568. Minimum Moves to Clean the Classroom

解題想法

中等難度題。題目給一個長度為 $m$ 的陣列 $classroom$，其中包含 $m$ 個長度為 $n$ 的字串，字串中只包含以下的字元：

• S 代表這格是學生的初位置
• L 代表這格有垃圾
• R 代表可以恢復能量的格子
• X 代表這格有障礙物，學生不能走到這格。
• . 代表空格

另外給一個整數 $energy$ 代表學生一開始的能量。假設學生每走一格消耗 1 點能量，如果能量歸零時不是位在 R 的格子上，學生無法再移動。如果學生走到 L 的格子上，可以撿起垃圾。如果學生走到 R 的格子上，會將能量補到起始值 $energy$。題目要問學生撿起所有垃圾時需要移動的最少步數，如果無法撿起所有的垃圾則回傳 $-1$。

這題的下方有提示，要用 BFS 解題，待走訪佇列放入的資料為 (x 座標, y 座標, 已撿起的垃圾狀態 mask, 目前的能量 e, 已走的步數 step)，並用一個三維陣列 bestEnergy 代表走到座標 (x, y) 時、狀態為 mask 的最高能量，並用 bestEnergy 剪枝。由於這題的垃圾數量上限為 10 個，可以先將每個位置的垃圾編號，用二進位制記錄這個編號的垃圾是否已被撿起來。詳細的 BFS 過程請參考程式碼中的註解。

Python 程式碼

Runtime: 1511 ms, beats 91.23%. Memory: 24.54 MB, beats 94.74%.

class Solution:
    def minMoves(self, classroom: List[str], energy: int) -> int:
        m, n = len(classroom), len(classroom[0])  # 教室尺寸 m*n
        # 1. 先找到起點 S 的位置、垃圾 L 的位置
        xi, yi = 0, 0  # S 的位置
        litter_pos = dict()  # 特定位置垃圾對應的編號
        litter_idx = 0   # 垃圾的編號
        for i in range(m):
            for j in range(n):
                ch = classroom[i][j]
                if ch == 'S':
                    xi, yi = i, j
                elif ch == 'L':
                    litter_pos[i, j] = litter_idx
                    litter_idx += 1
        
        total_litters = litter_idx  # 垃圾數量
        fullMask = (1 << total_litters) - 1  # 拿到所有垃圾的狀態
        
        # 特例，如果沒有垃圾，回傳 0
        if total_litters == 0: return 0
        
        # 2. BFS，待走訪佇列放入 (x 座標, y 座標, 狀態, 能量, 步數)
        que = deque([(xi, yi, 0, energy, 0)])
        # bestEnergy[x][y][mask] 代表走到 x, y, mask 狀態時最高的能量，預設為 -1
        bestEnergy = [[[-1] * (1 << total_litters) for _ in range(n)] for _ in range(m)]
        bestEnergy[xi][yi][0] = energy  # 起始狀態能量全滿
        # BFS
        while que:
            x, y, mask, e, step = que.popleft()
            # 如果 能量 e 為 0 且不在 R 上面，無法再移動
            if e == 0 and classroom[x][y] != 'R':
                continue
            # 四方位檢查
            for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                nx, ny = x + dx, y + dy
                # 如果沒有出界也沒有遇到障礙物 X
                if 0 <= nx < m and 0 <= ny < n and classroom[nx][ny] != 'X':
                    ne = e - 1  # 能量減 1
                    if ne < 0: continue  # 能量不足
                    nxt_mask = mask  # 新的狀態
                    if classroom[nx][ny] == 'L':  # 撿垃圾
                        nxt_mask |= (1 << litter_pos[nx, ny])  # 更新狀態
                    elif classroom[nx][ny] == 'R':  # 能量全滿
                        ne = energy
                    
                    # 如果 nxt_mask == fullMask，找到答案，回傳 step + 1
                    if nxt_mask == fullMask: return step + 1
                    
                    # 如果 ne 大於之前走到 [nx][ny][mask] 的能量，才將下一步加入 que
                    if ne > bestEnergy[nx][ny][nxt_mask]:
                        bestEnergy[nx][ny][nxt_mask] = ne
                        que.append((nx, ny, nxt_mask, ne, step + 1))
        # 如果走完 BFS 還沒有找到 fullMask，無法達成目標，回傳 -1
        return -1

C++ 程式碼

Runtime: 222 ms, beats 74.49%. Memory: 150.40 MB, beats 75.51%.

// 待走訪佇列的資料結構體
struct Data {
    int x, y, mask, energy, step;
    Data(int a, int b, int c, int d, int e) : x(a), y(b), mask(c), energy(d), step(e) {}
};

class Solution {
public:
    int minMoves(vector<string>& classroom, int energy) {
        /* 1. 先找到起點 S 的位置、垃圾 L 的位置 */
        int m = (int)classroom.size(), n = (int)classroom[0].size();
        map<pair<int, int>, int> litter_pos;  // 特定位置垃圾對應的編號
        int xi, yi, litter_idx = 0;  // S 的位置，垃圾的編號
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                char ch = classroom[i][j];
                if (ch == 'S') {
                    xi = i; yi = j;
                } else if (ch == 'L') {
                    litter_pos[make_pair(i, j)] = litter_idx;
                    litter_idx++;
                }
            }
        }

        int total_litters = litter_idx;  // 垃圾數量
        int fullMask = (1 << total_litters) - 1;  // 拿到所有垃圾的狀態

        // 特例，如果沒有垃圾，回傳 0
        if (total_litters == 0) return 0;

        /* 2. BFS，待走訪佇列放入 (x 座標, y 座標, 狀態, 能量, 步數) */
        // bestEnergy[x][y][mask] 代表走到 x, y, mask 狀態時最高的能量，預設為 -1
        vector<vector<vector<int>>> bestEnergy (m, vector<vector<int>> (n, vector<int> (1 << total_litters, -1)));
        bestEnergy[xi][yi][0] = energy;  // 起始狀態能量全滿
        
        // BFS
        int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
        queue<Data> que;
        que.push(Data(xi, yi, 0, energy, 0));
        while(!que.empty()) {
            auto it = que.front();
            int x = it.x, y = it.y, mask = it.mask, e = it.energy, step = it.step;
            que.pop();
            // 如果 能量 e 為 0 且不在 R 上面，無法再移動
            if (e == 0 && classroom[x][y] != 'R') continue;
            // 四方位檢查
            for(int k = 0; k < 4; k++) {
                int nx = x + dx[k], ny = y + dy[k];
                // 如果沒有出界也沒有遇到障礙物 X
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && classroom[nx][ny] != 'X') {
                    int ne = e - 1, nxt_mask = mask;  // 能量減 1，新的狀態
                    if (ne < 0) continue;  // 能量不足
                    char ch = classroom[nx][ny];
                    if (ch == 'L') {  // 撿垃圾
                        nxt_mask |= (1 << litter_pos[make_pair(nx, ny)]);
                    } else if (ch == 'R') {  // 能量全滿
                        ne = energy;
                    }
                    
                    // 如果 nxt_mask == fullMask，找到答案，回傳 step + 1
                    if (nxt_mask == fullMask) return step + 1;
                    
                    // 如果 ne 大於之前走到 [nx][ny][mask] 的能量，才將下一步加入 que
                    if (ne > bestEnergy[nx][ny][nxt_mask]) {
                        bestEnergy[nx][ny][nxt_mask] = ne;
                        que.push(Data(nx, ny, nxt_mask, ne, step + 1));
                    }
                }
            }
        }
        // 如果走完 BFS 還沒有找到 fullMask，無法達成目標，回傳 -1
        return -1;   
    }
};