Watch 6 video solutions for Minimum Moves to Clean the Classroom, a medium level problem involving Array, Hash Table, Bit Manipulation. This walkthrough by Tech Courses has 892 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 spaceYou 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:
(0, 0) with 2 units of energy.(1, 0) contains an obstacle 'X', the student cannot move directly downward.(0, 0) → (0, 1) with 1 unit of energy and 1 unit remaining.(0, 1) → (1, 1) to collect the litter 'L'.Example 2:
Input: classroom = ["LS", "RL"], energy = 4
Output: 3
Explanation:
(0, 1) with 4 units of energy.(0, 1) → (0, 0) to collect the first litter 'L' with 1 unit of energy used and 3 units remaining.(0, 0) → (1, 0) to 'R' to reset and restore energy back to 4.(1, 0) → (1, 1) to collect the second litter 'L'.Example 3:
Input: classroom = ["L.S", "RXL"], energy = 3
Output: -1
Explanation:
No valid path collects all 'L'.
Constraints:
1 <= m == classroom.length <= 201 <= n == classroom[i].length <= 20classroom[i][j] is one of 'S', 'L', 'R', 'X', or '.'1 <= energy <= 50'S' in the grid.'L' cells in the grid.Problem Overview: You are given a classroom grid where a robot must clean several dirty cells while avoiding obstacles. The robot moves one step at a time in four directions. The goal is to compute the minimum number of moves required to clean every dirty cell in the grid.
Approach 1: Permutation + BFS Distance (Brute Force) (Time: O(k! * m * n), Space: O(m * n))
First collect the starting position and all dirty cells. Compute the shortest distance between every pair of these points using Breadth-First Search. Then try every permutation of the dirty cells to determine the order in which the robot cleans them. For each order, sum the precomputed BFS distances. The minimum total distance across all permutations is the answer. This works because BFS guarantees the shortest path on a grid, but factorial permutations make it impractical when the number of dirty cells grows.
Approach 2: BFS with Bitmask State Compression (Optimal) (Time: O(m * n * 2^k), Space: O(m * n * 2^k))
Model the problem as a graph search where each state is (row, col, cleanedMask). The mask tracks which dirty cells have already been cleaned using bit manipulation. Start BFS from the robot's initial position with an empty mask. When the robot moves onto a dirty cell, update the corresponding bit in the mask. Continue exploring neighbors while tracking visited states to avoid repeating the same position with the same mask. Once the mask indicates all dirty cells are cleaned, the current BFS distance is the minimum number of moves.
The key insight: the robot's location alone is not enough to define progress. Two visits to the same cell can represent different states depending on which dirt spots were cleaned earlier. The bitmask encodes this progress efficiently, turning the problem into a shortest-path search over an expanded state graph.
This approach combines grid traversal using matrix movement with compact state tracking. BFS ensures the first time you reach a state that cleaned all cells, the number of moves is minimal.
Recommended for interviews: BFS with bitmask state compression. Interviewers expect you to recognize that the problem is essentially "visit all targets in a grid" and model it as BFS with a visited mask. Explaining the brute-force permutation idea first shows understanding of the search space, but the optimized BFS solution demonstrates strong algorithmic thinking and familiarity with state compression techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Permutation + BFS Distances | O(k! * m * n) | O(m * n) | Useful for understanding the problem and when the number of dirty cells is very small |
| BFS with Bitmask State | O(m * n * 2^k) | O(m * n * 2^k) | General case and expected interview solution for visiting multiple targets in a grid |