Minimum Moves to Clean the Classroom - Practice Coding Problems

Minimum Moves to Clean the Classroom - 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.

Input & Output

Example 1 — Basic Classroom

$ Input: classroom = [["S","L","R"],[".","X","L"]], energy = 3

› Output: 4

💡 Note: Start at (0,0), collect litter at (0,1) in 1 move, go to reset at (0,2) in 1 move to restore energy, then navigate to (1,2) to collect second litter in 2 moves. Total: 4 moves.

Example 2 — No Litter

$ Input: classroom = [["S",".","R"],[".","X","."]], energy = 2

› Output: 0

💡 Note: No litter to collect, so 0 moves required.

Example 3 — Impossible Case

$ Input: classroom = [["S","X","L"]], energy = 1

› Output: -1

💡 Note: Cannot reach the litter at (0,2) because obstacle at (0,1) blocks the path and we don't have enough energy to go around.

Constraints

1 ≤ m, n ≤ 20
1 ≤ energy ≤ 20
The grid contains exactly one 'S'
The number of 'L' cells is at most 10

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Grid with start (S), litter (L), reset (R), obstacles (X)

Pathfinding

Find minimum moves to collect all litter while managing energy

Result

Return minimum number of moves or -1 if impossible

Key Takeaway

🎯 Key Insight: Track position, collected items bitmask, and energy as a combined state in BFS

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is to use BFS with state tracking where each state includes position, collected litter bitmask, and current energy. The optimal approach is BFS with state encoding to ensure minimum moves. Time: O(m×n×2^L×E), Space: O(m×n×2^L×E).

Common Approaches

Approach	Time	Space	Notes
✓ BFS with State Tracking	O(m×n×2^L×E)	O(m×n×2^L×E)	Use BFS to explore states with position, collected items bitmask, and energy
Brute Force DFS with Backtracking	O(L! × 4^(m×n))	O(m×n)	Try all possible paths using DFS with backtracking

BFS with State Tracking — Algorithm Steps

Encode state as (position, collected_mask, energy)
Use BFS to explore all reachable states
Track visited states to avoid cycles
Return moves when all litter collected

Visualization

Tap to expand

Step-by-Step Walkthrough

Encode State

State = (position, collected_mask, energy)

BFS Exploration

Explore all reachable states level by level

Track Progress

Use bitmask to track which litter items collected

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef struct {
    int x, y, mask, energy, moves;
} State;

int solution(char** classroom, int m, int n, int energy) {
    int startX = -1, startY = -1;
    int litterPositions[20][2];
    int litterCount = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (classroom[i][j] == 'S') {
                startX = i;
                startY = j;
            } else if (classroom[i][j] == 'L') {
                litterPositions[litterCount][0] = i;
                litterPositions[litterCount][1] = j;
                litterCount++;
            }
        }
    }
    
    if (litterCount == 0) return 0;
    
    int targetMask = (1 << litterCount) - 1;
    
    // Simplified BFS implementation
    State queue[100000];
    int front = 0, rear = 0;
    
    queue[rear++] = (State){startX, startY, 0, energy, 0};
    
    int dirs[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    
    while (front < rear) {
        State curr = queue[front++];
        
        if (curr.mask == targetMask) {
            return curr.moves;
        }
        
        for (int d = 0; d < 4; d++) {
            int nx = curr.x + dirs[d][0];
            int ny = curr.y + dirs[d][1];
            
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && classroom[nx][ny] != 'X') {
                int newEnergy = curr.energy - 1;
                if (newEnergy < 0) continue;
                
                int newMask = curr.mask;
                
                // Check if this is a litter position
                for (int i = 0; i < litterCount; i++) {
                    if (litterPositions[i][0] == nx && litterPositions[i][1] == ny) {
                        newMask |= (1 << i);
                        break;
                    }
                }
                
                if (classroom[nx][ny] == 'R') {
                    newEnergy = energy;
                }
                
                if (rear < 100000) {
                    queue[rear++] = (State){nx, ny, newMask, newEnergy, curr.moves + 1};
                }
            }
        }
    }
    
    return -1;
}

int main() {
    char** classroom = NULL;
    int m = 0, n = 0;
    int energy;
    
    // Simplified input parsing
    scanf("%d", &energy);
    
    int result = solution(classroom, m, n, energy);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n×2^L×E)

BFS visits each cell with each possible combination of collected litter (2^L) and energy levels (E)

✓ Linear Growth

Space Complexity

O(m×n×2^L×E)

Store visited states for each position, litter collection mask, and energy level

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS with State Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler