# Minimum Moves to Clean the Classroom
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-moves-to-clean-the-classroom)
Canonical: https://scaleengineer.com/dsa/problems/minimum-moves-to-clean-the-classroom
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Hash Table, Matrix
---
## Problem
You are given an `m x n` grid `classroom` where a student volunteer is tasked with cleaning up litter scattered around the room. Each cell in the grid is one of the following:

* `'S'`: Starting position of the student
* `'L'`: Litter that must be collected (once collected, the cell becomes empty)
* `'R'`: Reset area that restores the student's energy to full capacity, regardless of their current energy level (can be used multiple times)
* `'X'`: Obstacle the student cannot pass through
* `'.'`: Empty space

You are also given an integer `energy`, representing the student's maximum energy capacity. The student starts with this energy from the starting position `'S'`.

Each move to an adjacent cell (up, down, left, or right) costs 1 unit of energy. If the energy reaches 0, the student can only continue if they are on a reset area `'R'`, which resets the energy to its **maximum** capacity `energy`.

Return the **minimum** number of moves required to collect all litter items, or `-1` if it's impossible.

**Example 1:**

**Input:** classroom = \["S.", "XL"\], energy = 2

**Output:** 2

**Explanation:**

* The student starts at cell `(0, 0)` with 2 units of energy.
* Since cell `(1, 0)` contains an obstacle 'X', the student cannot move directly downward.
* A valid sequence of moves to collect all litter is as follows:  
  * Move 1: From `(0, 0)` → `(0, 1)` with 1 unit of energy and 1 unit remaining.
  * Move 2: From `(0, 1)` → `(1, 1)` to collect the litter `'L'`.
* The student collects all the litter using 2 moves. Thus, the output is 2.

**Example 2:**

**Input:** classroom = \["LS", "RL"\], energy = 4

**Output:** 3

**Explanation:**

* The student starts at cell `(0, 1)` with 4 units of energy.
* A valid sequence of moves to collect all litter is as follows:  
  * Move 1: From `(0, 1)` → `(0, 0)` to collect the first litter `'L'` with 1 unit of energy used and 3 units remaining.
  * Move 2: From `(0, 0)` → `(1, 0)` to `'R'` to reset and restore energy back to 4.
  * Move 3: From `(1, 0)` → `(1, 1)` to collect the second litter `'L'`.
* The student collects all the litter using 3 moves. Thus, the output is 3.

**Example 3:**

**Input:** classroom = \["L.S", "RXL"\], energy = 3

**Output:** \-1

**Explanation:**

No valid path collects all `'L'`.

**Constraints:**

* `1 <= m == classroom.length <= 20`
* `1 <= n == classroom[i].length <= 20`
* `classroom[i][j]` is one of `'S'`, `'L'`, `'R'`, `'X'`, or `'.'`
* `1 <= energy <= 50`
* There is exactly **one** `'S'` in the grid.
* There are **at most** 10 `'L'` cells in the grid.

# Approaches
## Brute-Force Backtracking
This approach involves exploring every possible path the student can take from the starting position. It uses a recursive (or depth-first search) strategy to navigate the grid. For every state defined by the student's position, collected litter, and current energy, it tries moving to all valid adjacent cells.
**Time:** Exponential, roughly O(4^P) where P is the maximum possible path length. This is because at each step, we can branch out in up to 4 directions. This will time out on most test cases. · **Space:** O(P) for the recursion stack depth, where P is the maximum path length.
**Pros:** Conceptually simple and easy to write.
**Cons:** Extremely inefficient due to re-computation of states.; Not feasible for the given constraints.
### Explanation
A recursive function, say `findMinMoves(row, col, mask, energy, moves)`, is defined to perform the search. The state is described by the current `(row, col)`, a bitmask `mask` for collected litter, the remaining `energy`, and the total `moves` taken so far.

From a given state, the function recursively calls itself for all four adjacent cells (up, down, left, right), provided the move is valid (within grid bounds, not an obstacle, and sufficient energy). When a move is made, the `moves` count is incremented, and `energy` is decremented. If the new cell contains litter, the `mask` is updated. If it's a reset area, energy is restored to the maximum.

A global variable, `minTotalMoves`, is used to keep track of the minimum moves found so far to collect all litter. Whenever a state is reached where all litter is collected (i.e., the mask is full), `minTotalMoves` is updated.

This method does not use memoization, meaning it may re-compute paths for the same state `(row, col, mask, energy)` multiple times, leading to an extremely high number of redundant calculations.
### Algorithm
1.  Initialize a global variable `minMoves` to infinity.
2.  Identify the starting position 'S' and the locations of all 'L' litter items.
3.  Define a recursive function `backtrack(r, c, mask, energy, currentMoves)`.
4.  **Base Case:** If `mask` indicates all litter has been collected, update `minMoves = min(minMoves, currentMoves)` and return.
5.  **Pruning:** If `currentMoves >= minMoves`, return, as this path cannot be better.
6.  **Recursive Step:** For each of the 4 neighbors `(nr, nc)`:
    a. Check if the move is valid (in bounds, not 'X').
    b. Calculate the energy after the move: `newEnergy = energy - 1`.
    c. If `newEnergy < 0`, the move is not possible. Continue.
    d. Determine the new mask `newMask` and final energy `finalEnergy` based on the cell type at `(nr, nc)`.
    e. Recursively call `backtrack(nr, nc, newMask, finalEnergy, currentMoves + 1)`.
7.  Start the process by calling `backtrack(startR, startC, 0, maxEnergy, 0)`.
8.  After the recursion completes, if `minMoves` is still infinity, it's impossible; otherwise, `minMoves` is the answer.

```java
class Solution {
    int minMoves = Integer.MAX_VALUE;
    int m, n, maxEnergy, targetMask;
    char[][] grid;
    int[][] litterCoords;
    int[] dr = {-1, 1, 0, 0};
    int[] dc = {0, 0, -1, 1};

    public int minimumMoves(String[] classroom, int energy) {
        // ... initialization of grid, m, n, maxEnergy, litterCoords, targetMask ...
        // For simplicity, this part is omitted. Assume they are set up.
        // backtrack(startR, startC, 0, maxEnergy, 0);
        // return minMoves == Integer.MAX_VALUE ? -1 : minMoves;
        return -1; // Placeholder for full implementation
    }

    void backtrack(int r, int c, int mask, int currentEnergy, int moves) {
        if (moves >= minMoves) {
            return;
        }
        if (mask == targetMask) {
            minMoves = Math.min(minMoves, moves);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 'X') {
                if (currentEnergy > 0) {
                    int nextEnergy = currentEnergy - 1;
                    int nextMask = mask;
                    char cell = grid[nr][nc];

                    if (cell == 'L') {
                        for (int j = 0; j < litterCoords.length; j++) {
                            if (litterCoords[j][0] == nr && litterCoords[j][1] == nc) {
                                nextMask |= (1 << j);
                                break;
                            }
                        }
                    } else if (cell == 'R') {
                        nextEnergy = maxEnergy;
                    }
                    backtrack(nr, nc, nextMask, nextEnergy, moves + 1);
                }
            }
        }
    }
}
```

## TSP-style Dynamic Programming
This approach models the problem as a variation of the Traveling Salesperson Problem (TSP). The 'cities' to visit are the starting point 'S' and all litter locations 'L'. The cost of traveling between these points is not fixed; it depends on the student's energy and the availability of reset points 'R'.
**Time:** O((k + num_R) * m * n + k^2 * 2^k * num_R), where `k` is the number of litters and `num_R` is the number of reset points. The first term is for pre-computation, the second for the DP calculation. This can be slower than the full BFS if `num_R` is large. · **Space:** O((k + num_R) * m * n) to store the pre-computed distances. The DP table itself takes O(k * 2^k) space. This is generally much more memory-efficient than the full BFS approach.
**Pros:** Significantly more efficient than brute-force.; Uses much less memory than a full state-space BFS.; Can be faster than BFS if the number of reset points is small.
**Cons:** Much more complex to implement correctly.; Performance is sensitive to the number of reset points (`num_R`), and can be slow if `num_R` is large.
### Explanation
First, we pre-compute the shortest path distances (number of moves) between all pairs of important locations: 'S', all 'L's, and all 'R's. This is done by running a Breadth-First Search (BFS) from each of these locations.

Then, we use dynamic programming. The state is defined by `dp[i][mask]`, which stores a pair `(moves, energy)` representing the best outcome for collecting the set of litters in `mask` and ending at litter `i`. 'Best' is defined lexicographically: we want to minimize `moves`, and for an equal number of moves, we want to maximize the remaining `energy`.

The DP transition involves iterating from a previously visited litter `j` (in `mask`) to a new litter `i` (not in `mask`). The cost of this `j -> i` transition is calculated by considering two possibilities:
1.  A direct path from `j` to `i`, if there's enough energy.
2.  A path from `j` to `i` via the most optimal reset point `R`, which minimizes `dist(j, R) + dist(R, i)`.

The DP table is updated if a new path to `(i, new_mask)` is better (fewer moves, or same moves with more energy). The final answer is the minimum moves found across all final states `dp[i][(1<<k)-1]`.
### Algorithm
1.  Identify all Points of Interest (POIs): 'S' and all 'L's. Also, find all 'R' locations.
2.  Pre-computation: Run BFS from each POI and each 'R' to calculate all-pairs shortest path distances `dist(p1, p2)`.
3.  Initialize a DP table `dp[k][1<<k]` where `k` is the number of litters. `dp[i][mask]` stores a pair `(moves, energy)`.
4.  Base Cases: For each litter `i`, calculate the cost to go from 'S' to `L_i` (directly or via an 'R' point) and initialize `dp[i][1<<i]`.
5.  Iterate through `mask` from 1 to `(1<<k)-1`.
6.  For each `i` where `L_i` is in `mask`:
7.  For each `j` where `L_j` is not in `mask`:
    a. Calculate the cost `(new_moves, new_energy)` to travel from `L_i` to `L_j` starting with energy `dp[i][mask].energy`.
    b. This involves checking the direct path and all paths via reset points.
    c. If this new path to `L_j` is better than the existing `dp[j][mask | (1<<j)]`, update it.
8.  The result is the minimum `moves` among all `dp[i][(1<<k)-1]` for `i=0..k-1`.

```java
class Solution {
    // Assuming pre-computed distances: dist[poi1_idx][poi2_idx]
    // Pair class for (moves, energy)
    class State {
        int moves, energy;
        State(int m, int e) { this.moves = m; this.energy = e; }
    }

    public int minimumMoves(String[] classroom, int energy) {
        // ... setup: find POIs, Rs, pre-compute distances ...
        int k = /* number of litters */; 
        int numPois = k + 1; // S + L's
        State[][] dp = new State[k][1 << k];
        // ... initialize dp table with (infinity, -1) ...

        // Base cases: S -> L_i
        for (int i = 0; i < k; i++) {
            // Calculate cost from S (POI 0) to L_i (POI i+1)
            // dp[i][1 << i] = calculateInitialState(i, energy);
        }

        for (int mask = 1; mask < (1 << k); mask++) {
            for (int i = 0; i < k; i++) {
                if ((mask & (1 << i)) != 0) { // If L_i is in mask
                    if (dp[i][mask].moves == Integer.MAX_VALUE) continue;

                    for (int j = 0; j < k; j++) {
                        if ((mask & (1 << j)) == 0) { // If L_j is not in mask
                            int nextMask = mask | (1 << j);
                            // State state = calculateTransition(i, j, dp[i][mask], energy);
                            // if (isBetter(state, dp[j][nextMask])) {
                            //     dp[j][nextMask] = state;
                            // }
                        }
                    }
                }
            }
        }

        int minTotalMoves = Integer.MAX_VALUE;
        for (int i = 0; i < k; i++) {
            minTotalMoves = Math.min(minTotalMoves, dp[i][(1 << k) - 1].moves);
        }

        return minTotalMoves == Integer.MAX_VALUE ? -1 : minTotalMoves;
    }
}
```

## Breadth-First Search on the Full State Space
This approach treats the problem as finding the shortest path in a state graph. Since each move has a uniform cost of 1, Breadth-First Search (BFS) is the ideal algorithm. The key is to define the state comprehensively to capture all necessary information for making decisions.
**Time:** O(m * n * 2^k * energy). The time complexity is proportional to the number of states, as BFS visits each state at most once. `m, n` are grid dimensions, `k` is the number of litters. · **Space:** O(m * n * 2^k * energy). This is dominated by the `dist` array used to store the minimum moves to each state and prevent cycles.
**Pros:** Guaranteed to find the shortest path in terms of moves.; Conceptually straightforward application of BFS on a state graph.; More robust and often faster than the TSP DP approach for the given constraints, especially when the number of reset points is high.
**Cons:** High memory usage due to the large state space. Could be an issue if constraints were larger.
### Explanation
The state in our BFS needs to track not just the student's position, but also which litter has been collected and the current energy level. Thus, a state is represented by a tuple: `(row, col, mask, energy)`.

- `(row, col)`: The student's current coordinates.
- `mask`: A bitmask where the i-th bit is set if the i-th litter has been collected.
- `energy`: The student's current energy.

We use a queue to perform the BFS and a multi-dimensional array, `dist[row][col][mask][energy]`, to store the minimum moves to reach each state. This `dist` array also serves as a `visited` set to prevent cycles and redundant computations.

The BFS starts with the initial state: `(start_row, start_col, 0, max_energy)`. In each step, we dequeue a state and explore its neighbors. For each valid move, we calculate the new state (updated position, mask, and energy). If we land on a reset 'R' cell, the energy is restored to its maximum. If this new state is reached with fewer moves than recorded in `dist`, we update `dist` and enqueue the new state.

The search terminates as soon as we reach any state where all litter has been collected (i.e., `mask` is full). The number of moves to reach this state is the minimum possible.
### Algorithm
1.  Map each litter 'L' to a unique bit index from 0 to `k-1`, where `k` is the total number of litters. The target mask will be `(1 << k) - 1`.
2.  Find the starting 'S' coordinates `(startR, startC)`.
3.  Initialize a queue for BFS and a 4D array `dist[m][n][1<<k][energy+1]` with infinity.
4.  Set the initial state: `dist[startR][startC][0][maxEnergy] = 0` and add `(startR, startC, 0, maxEnergy)` to the queue.
5.  While the queue is not empty:
    a. Dequeue the current state `(r, c, mask, e)`.
    b. If `mask == targetMask`, we have collected all litter. Return `dist[r][c][mask][e]`.
    c. For each of the 4 neighbors `(nr, nc)`:
        i. Check if the move is valid (in bounds, not 'X', and `e > 0`).
        ii. Calculate the state after the move: `newMoves = dist[r][c][mask][e] + 1`, `newEnergy = e - 1`, `newMask = mask`.
        iii. If `grid[nr][nc] == 'L'`, update `newMask` by setting the corresponding bit.
        iv. If `grid[nr][nc] == 'R'`, set `newEnergy = maxEnergy`.
        v. If `newMoves < dist[nr][nc][newMask][newEnergy]`, update `dist[nr][nc][newMask][newEnergy] = newMoves` and enqueue the new state `(nr, nc, newMask, newEnergy)`.
6.  If the queue becomes empty and we haven't found a solution, it's impossible. Return -1.

```java
class Solution {
    public int minimumMoves(String[] classroom, int energy) {
        int m = classroom.length;
        int n = classroom[0].length();
        List<int[]> litters = new ArrayList<>();
        int startR = -1, startC = -1;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (classroom[i].charAt(j) == 'L') {
                    litters.add(new int[]{i, j});
                } else if (classroom[i].charAt(j) == 'S') {
                    startR = i;
                    startC = j;
                }
            }
        }

        int k = litters.size();
        if (k == 0) return 0;
        int targetMask = (1 << k) - 1;

        int[][][][] dist = new int[m][n][1 << k][energy + 1];
        for (int[][][] a1 : dist) for (int[][] a2 : a1) for (int[] a3 : a2) Arrays.fill(a3, -1);

        Queue<int[]> queue = new LinkedList<>();
        // state: {r, c, mask, energy}
        queue.offer(new int[]{startR, startC, 0, energy});
        dist[startR][startC][0][energy] = 0;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0], c = curr[1], mask = curr[2], e = curr[3];
            int moves = dist[r][c][mask][e];

            if (mask == targetMask) return moves;

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n && classroom[nr].charAt(nc) != 'X') {
                    if (e > 0) {
                        int ne = e - 1;
                        int nMask = mask;
                        char cell = classroom[nr].charAt(nc);

                        if (cell == 'L') {
                            for (int j = 0; j < k; j++) {
                                if (litters.get(j)[0] == nr && litters.get(j)[1] == nc) {
                                    nMask |= (1 << j);
                                    break;
                                }
                            }
                        } 
                        if (cell == 'R') {
                            ne = energy;
                        }

                        if (dist[nr][nc][nMask][ne] == -1) {
                            dist[nr][nc][nMask][ne] = moves + 1;
                            queue.offer(new int[]{nr, nc, nMask, ne});
                        }
                    }
                }
            }
        }
        return -1;
    }
}
```

# Solutions
### Java

```java
class Solution {
public
  int minMoves(String[] classroom, int energy) {
    int m = classroom.length, n = classroom[0].length();
    int[][] d = new int[m][n];
    int x = 0, y = 0, cnt = 0;
    for (int i = 0; i < m; i++) {
      String row = classroom[i];
      for (int j = 0; j < n; j++) {
        char c = row.charAt(j);
        if (c == 'S') {
          x = i;
          y = j;
        } else if (c == 'L') {
          d[i][j] = cnt;
          cnt++;
        }
      }
    }
    if (cnt == 0) {
      return 0;
    }
    boolean[][][][] vis = new boolean[m][n][energy + 1][1 << cnt];
    List<int[]> q = new ArrayList<>();
    q.add(new int[]{x, y, energy, (1 << cnt) - 1});
    vis[x][y][energy][(1 << cnt) - 1] = true;
    int[] dirs = {-1, 0, 1, 0, -1};
    int ans = 0;
    while (!q.isEmpty()) {
      List<int[]> t = q;
      q = new ArrayList<>();
      for (int[] state : t) {
        int i = state[0], j = state[1], curEnergy = state[2], mask = state[3];
        if (mask == 0) {
          return ans;
        }
        if (curEnergy <= 0) {
          continue;
        }
        for (int k = 0; k < 4; k++) {
          int nx = i + dirs[k], ny = j + dirs[k + 1];
          if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
              classroom[nx].charAt(ny) != 'X') {
            int nxtEnergy =
                classroom[nx].charAt(ny) == 'R' ? energy : curEnergy - 1;
            int nxtMask = mask;
            if (classroom[nx].charAt(ny) == 'L') {
              nxtMask &= ~(1 << d[nx][ny]);
            }
            if (!vis[nx][ny][nxtEnergy][nxtMask]) {
              vis[nx][ny][nxtEnergy][nxtMask] = true;
              q.add(new int[]{nx, ny, nxtEnergy, nxtMask});
            }
          }
        }
      }
      ans++;
    }
    return -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minMoves(vector<string> &classroom, int energy) {
    int m = classroom.size(), n = classroom[0].size();
    vector<vector<int>> d(m, vector<int>(n, 0));
    int x = 0, y = 0, cnt = 0;
    for (int i = 0; i < m; ++i) {
      string &row = classroom[i];
      for (int j = 0; j < n; ++j) {
        char c = row[j];
        if (c == 'S') {
          x = i;
          y = j;
        } else if (c == 'L') {
          d[i][j] = cnt;
          cnt++;
        }
      }
    }
    if (cnt == 0) {
      return 0;
    }
    vector<vector<vector<vector<bool>>>> vis(
        m, vector<vector<vector<bool>>>(
               n, vector<vector<bool>>(energy + 1,
                                       vector<bool>(1 << cnt, false))));
    queue<tuple<int, int, int, int>> q;
    q.emplace(x, y, energy, (1 << cnt) - 1);
    vis[x][y][energy][(1 << cnt) - 1] = true;
    vector<int> dirs = {-1, 0, 1, 0, -1};
    int ans = 0;
    while (!q.empty()) {
      int sz = q.size();
      while (sz--) {
        auto [i, j, cur_energy, mask] = q.front();
        q.pop();
        if (mask == 0) {
          return ans;
        }
        if (cur_energy <= 0) {
          continue;
        }
        for (int k = 0; k < 4; ++k) {
          int nx = i + dirs[k], ny = j + dirs[k + 1];
          if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
              classroom[nx][ny] != 'X') {
            int nxt_energy = classroom[nx][ny] == 'R' ? energy : cur_energy - 1;
            int nxt_mask = mask;
            if (classroom[nx][ny] == 'L') {
              nxt_mask &= ~(1 << d[nx][ny]);
            }
            if (!vis[nx][ny][nxt_energy][nxt_mask]) {
              vis[nx][ny][nxt_energy][nxt_mask] = true;
              q.emplace(nx, ny, nxt_energy, nxt_mask);
            }
          }
        }
      }
      ans++;
    }
    return -1;
  }
};

```

### Python

```python
class Solution:
    def minMoves(self, classroom: List[str], energy: int) -> int: m, n = len(classroom), len(classroom[0]) d = [[0] * n for _ in range(m)] x = y = cnt = 0 for i, row in enumerate(classroom): for j, c in enumerate(row): if c == "S": x, y = i, j elif c == "L": d[i][j] = cnt cnt += 1 if cnt == 0: return 0 vis = [[[[False] * (1 << cnt) for _ in range(energy + 1)] for _ in range(n)] for _ in range(m)] q = [(x, y, energy, (1 << cnt) - 1)] vis[x][y][energy][(1 << cnt) - 1] = True dirs = (- 1, 0, 1, 0, - 1) ans = 0 while q: t = q q = [] for i, j, cur_energy, mask in t: if mask == 0: return ans if cur_energy <= 0: continue for k in range(4): x, y = i + dirs[k], j + dirs[k + 1] if 0 <= x < m and 0 <= y < n and classroom[x][y] != "X": nxt_energy = (energy if classroom[x][y] == "R" else cur_energy - 1) nxt_mask = mask if classroom[x][y] == "L": nxt_mask &= ~ (1 << d[x][y]) if not vis[x][y][nxt_energy][nxt_mask]: vis[x][y][nxt_energy][nxt_mask] = True q . append((x, y, nxt_energy, nxt_mask)) ans += 1 return - 1

```