405. Minimum Moves to Clean the Classroom

Search the graph of situations the student can be in — not just the cell, but which litter is already collected and how much energy is left. BFS over that expanded state finds the fewest moves.

Why a plain grid BFS is not enough

On an ordinary shortest-path grid, a cell is either visited or not. Here the same cell can matter many times: reaching (r, c) after you have already picked up two pieces of litter is a genuinely different situation from reaching it with none, and reaching it with 5 energy left beats reaching it with 1. So a "state" is the full triple:

state = (row, col, collected_mask, energy_left)

collected_mask is a bitmask over the litter cells (at most 10 of them, so 2^10 = 1024 masks). The answer is the fewest moves to reach any state whose mask has every litter bit set.

The algorithm — BFS with an energy-domination rule

Every move costs exactly one step, so breadth-first search explores states in increasing number of moves and the first time we pop a fully-collected mask is the minimum.

1. Index each 'L' cell 0, 1, 2, ...; full = (1 << L) - 1. If there is no litter, the answer is 0.
2. Seed the queue with the start: (sr, sc, mask = 0, energy_left = energy).
3. Pop a state. If its mask equals full, return the current move count.
4. Otherwise, if it has energy left, try all four neighbours that are not 'X':
   • Moving costs 1 energy: ne = energy_left - 1.
   • If the neighbour is 'L', set its bit in the mask.
   • If the neighbour is 'R', the tank refills: ne = energy (max).
5. Domination / pruning: keep best[r][c][mask] = the most energy ever seen at that (cell, mask). Only enqueue a neighbour state if it arrives with strictly more energy than the best recorded there. A state with more energy can do everything a lower-energy one could, so the lower one is safe to discard — this is what keeps the search finite and fast.

Worked example

classroom = ["LS", "RL"], energy = 4. Litter cells: (0,0) -> bit 0, (1,1) -> bit 1, so full = 0b11 = 3. Start S is (0,1).

The fully-collected state is first reached after 3 moves, so the answer is 3. Without the reset at (1,0) the student would have run out of energy before reaching the far litter.

Complexity

Let S = number of litter cells (<= 10).

• Time: O(m·n · 2^S · energy) — one BFS state per (cell, mask, energy level).
• Space: O(m·n · 2^S) for the best energy table.

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int minMoves(String[] classroom, int energy) {
        int m = classroom.length, n = classroom[0].length();

        // Index every litter cell so its "collected" bit lives in a bitmask.
        int[][] litterIndex = new int[m][n];
        for (int[] row : litterIndex) {
            java.util.Arrays.fill(row, -1);
        }
        int totalLitter = 0, sr = 0, sc = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                char ch = classroom[r].charAt(c);
                if (ch == 'L') {
                    litterIndex[r][c] = totalLitter++;
                } else if (ch == 'S') {
                    sr = r;
                    sc = c;
                }
            }
        }

        int full = (1 << totalLitter) - 1;
        if (totalLitter == 0) {
            return 0;
        }

        // best[r][c][mask] = most energy ever seen at that (cell, collected-set).
        int[][][] best = new int[m][n][full + 1];
        for (int[][] plane : best) {
            for (int[] row : plane) {
                java.util.Arrays.fill(row, -1);
            }
        }
        best[sr][sc][0] = energy;

        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{sr, sc, 0, energy});
        int moves = 0;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int r = cur[0], c = cur[1], mask = cur[2], e = cur[3];
                if (mask == full) {
                    return moves;
                }
                if (e == 0) {
                    continue;  // out of energy on a non-reset cell — stuck
                }
                for (int[] d : directions) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
                        continue;
                    }
                    char cell = classroom[nr].charAt(nc);
                    if (cell == 'X') {
                        continue;
                    }
                    int ne = e - 1;
                    int nmask = mask;
                    if (cell == 'L') {
                        nmask = mask | (1 << litterIndex[nr][nc]);
                    } else if (cell == 'R') {
                        ne = energy;  // reset pad refills to full capacity
                    }
                    // Only keep this state if it arrives with strictly more energy
                    // than anything seen before at the same cell + collected-set.
                    if (ne > best[nr][nc][nmask]) {
                        best[nr][nc][nmask] = ne;
                        queue.offer(new int[]{nr, nc, nmask, ne});
                    }
                }
            }
            moves++;
        }

        return -1;
    }
}