Skip to main content
Talentd

Minimum Moves to Clean the Classroom - Solution & Explanation

MediumArrayHash TableBit ManipulationBreadth-First Search12 min readAsked at: Bloomberg
Practice this problem

Problem Statement

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.

Approach Overview

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.

Solution

We can use Breadth-First Search (BFS) to solve this problem. First, we need to find the student's starting position and record the locations of all garbage. Then, we can use BFS to explore all possible paths starting from the initial position, while tracking the current energy and the collected garbage.

In BFS, we need to maintain a state that includes the current position, remaining energy, and a bitmask representing the collected garbage. We can use a queue to store these states and a set to record visited states to avoid revisiting them.

We start from the initial position and try to move in four directions. If we move to a garbage cell, we update the collected garbage bitmask. If we move to a reset area, we restore the energy to its maximum value. Each move consumes 1 unit of energy.

If we find a state in BFS where the garbage bitmask is 0 (meaning all garbage has been collected), we return the current number of moves. If BFS completes without finding such a state, we return -1.

The time complexity is O(m times n times energy times 2^{count}), and the space complexity is O(m times n times energy times 2^{count}), where m and n are the number of rows and columns in the grid, and count is the number of garbage cells.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Permutation + BFS DistancesO(k! * m * n)O(m * n)Useful for understanding the problem and when the number of dirty cells is very small
BFS with Bitmask StateO(m * n * 2^k)O(m * n * 2^k)General case and expected interview solution for visiting multiple targets in a grid

Video Solution

3568. Minimum Moves to Clean the Classroom | Weekly 452 | 3rd Problem • Tech Courses • 928 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Minimum Moves to Clean the Classroom easy or hard?
Minimum Moves to Clean the Classroom is considered a medium difficulty problem. The grid BFS itself is straightforward, but the challenge comes from tracking which dirty cells are cleaned using a bitmask and preventing repeated states during traversal.
Minimum Moves to Clean the Classroom Python/Java solution
The typical implementation performs BFS using a queue storing (row, col, mask, distance). When the robot reaches a dirty cell, update the mask with bit manipulation and push the new state into the queue. This approach is straightforward to implement in Python, Java, C++, and Go using standard BFS templates.
How to solve Minimum Moves to Clean the Classroom in O(m*n*2^k)?
Use BFS where the state contains the current row, column, and a bitmask of cleaned cells. Start from the robot's position and explore the four directions in the grid. When stepping on a dirty cell, update the mask using bit operations. Once the mask equals the value representing all cells cleaned, the BFS level gives the minimum number of moves.
What is the best approach for Minimum Moves to Clean the Classroom?
The most efficient approach uses Breadth-First Search with bitmask state compression. Each BFS state tracks the robot's position and a bitmask representing which dirty cells are already cleaned. This allows the algorithm to explore all possible cleaning paths while guaranteeing the shortest number of moves. The complexity is O(m * n * 2^k), where k is the number of dirty cells.
Is Minimum Moves to Clean the Classroom asked at Google/Amazon/Meta?
Grid traversal combined with BFS and bitmask state compression is a common pattern in Google, Amazon, and Meta interviews. Problems that require visiting multiple targets in a grid frequently appear in onsite rounds because they test graph traversal, state modeling, and optimization skills.
What data structure is used in Minimum Moves to Clean the Classroom?
The solution relies on a queue for Breadth-First Search, a bitmask integer to track cleaned cells, and a visited set or 3D boolean structure to avoid revisiting the same state. The grid itself is treated as a matrix where movement occurs in four directions.
What is the time complexity of Minimum Moves to Clean the Classroom?
The optimal BFS with bitmask solution runs in O(m * n * 2^k) time and uses O(m * n * 2^k) space. The grid positions contribute m * n states, and the bitmask introduces 2^k combinations for k dirty cells. Brute-force permutation approaches can reach O(k! * m * n), which becomes infeasible for larger k.

Ready to solve this problem?

Practice Minimum Moves to Clean the Classroom with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays