Minimum Moves to Clean the Classroom

Minimum Moves to Clean the Classroom

1. What is this problem about?

Imagine a grid representing a classroom where some cells are dirty (marked with 1s) and others are clean (0s). You have a cleaning robot that can move up, down, left, or right. The robot starts at a specific position. Some cells might also be "obstacles" that the robot cannot pass through.

The objective is to find the minimum number of moves to visit and clean all the dirty cells. This is a classic "Traveling Salesman Problem" (TSP) variant on a grid.

2. Why is this asked in interviews?

Bloomberg asks this to test a candidate's ability to combine BFS with Dynamic Programming (Bitmask). Key evaluation points:

• Pathfinding: Using BFS to find the shortest distance between all pairs of dirty cells.
• State Compression: Using a Bitmask to represent the set of cleaned cells.
• Complex DP: Solving the TSP problem efficiently when the number of dirty cells is small (usually $\le 15$).

3. Algorithmic pattern used

The pattern is BFS + DP with Bitmask.

1. Precompute Distances: For every dirty cell (and the starting position), run a BFS to find the shortest distance to every other dirty cell. Store these in a distance matrix.
2. DP State: dp(current_cell_index, mask), where mask is a bitmask where the i-th bit is 1 if the i-th dirty cell has been cleaned.
3. Transition: From current_cell_index, try moving to any unvisited dirty cell j (where mask & (1 << j) == 0).
4. Base Case: If the mask is all 1s (all cells cleaned), return 0.

4. Example explanation

Start: (0, 0), Dirty cells: A(0, 2), B(2, 0)

• BFS from Start: dist to A = 2, dist to B = 2.
• BFS from A: dist to B = 4. Possible orders:

1. Start $\rightarrow$ A $\rightarrow$ B: $2 + 4 = 6$ moves.
2. Start $\rightarrow$ B $\rightarrow$ A: $2 + 4 = 6$ moves. Minimum moves = 6.

5. Common mistakes candidates make

• Pure BFS: Trying to use a single BFS where the state is (x, y, mask). While correct, it can be very slow if the grid is large.
• Missing Obstacles: Not accounting for the fact that the shortest distance between two dirty cells isn't just the Manhattan distance if there are walls.
• TSP Complexity: Forgetting that TSP is NP-hard. This only works if the number of dirty cells is small.

6. Interview preparation tip

Learn "Bitmask DP." It is the standard way to solve problems that involve "visiting all nodes" or "picking a subset" when the number of items is small. Combining it with BFS for distance precomputation is a very common "Hard" interview pattern.