3568. Minimum Moves to Clean the Classroom

MediumBit ManipulationBreadth-First SearchArrayHash TableMatrix

Problem Description

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

This problem asks how to collect all litter items in a grid while managing the student's energy, obstacles, and reset points. Since every movement decreases energy and only specific cells can refill it, we need to keep track of both energy and which litter items have already been collected.

A good way to think about the problem is as exploring all possible paths in the grid, not just from point A to B, but also tracking:

Where you are in the grid
How much energy you have left
Which pieces of litter are still left

The process is similar to searching through a maze with special rules. Breadth-First Search (BFS) is well-suited for this, as it can find the shortest path while keeping track of extra information—here, that's the current energy and a bitmask to record which litter has been collected.

By exploring moves in all directions at every step and restoring energy at reset areas, we can exhaust all paths while remembering which paths and situations we've already explored, so we don’t repeat unnecessary work. As soon as all litter is collected, the current number of moves gives the answer. If there’s no way to collect them all, we recognize that as well.

Solution Approach

We use Breadth-First Search (BFS) to find the shortest path that allows the student to collect all litter with the given energy constraints.

State Representation: Each BFS state includes:

The current position (x, y) in the grid.
The current amount of energy remaining.
A bitmask representing which litter pieces are left to collect.

Grid Parsing:

First, scan the grid for the start position 'S' and all litter locations 'L'.
Assign each litter location a unique bit in the bitmask.

Visited States: To avoid revisiting the same state, we keep a 4D visited array: visited[x][y][energy][mask] is True if we have been at position (x, y) with energy and have mask for litter left.

BFS Steps:

Initialize the BFS queue with the start position, full energy, and a mask marking all litter as uncollected.
For every move, explore the four directions (up, down, left, right):
- Make sure the cell is within bounds and not an obstacle.
- Update energy:
  - If stepping on 'R', reset energy to max.
  - Otherwise, subtract 1 from energy.
- If stepping on 'L', update the bitmask by marking this litter as collected.
Only enqueue states not seen before.
Stop and return the number of moves when the bitmask becomes 0 (all litter collected).
If BFS completes without collecting all litter, return -1.

Key Data Structures:

BFS queue to process states level-by-level (guaranteeing shortest path).
Bitmasking for efficient tracking of collected litter.

Pattern Used:

Multi-dimensional BFS with extra state (energy and bitmask).

This approach ensures every move is tracked with respect to both the path taken and energy constraints, providing the minimal steps to complete the task or confirming when it's impossible.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider this grid, with energy = 4:

S . L
X R .
L . .

Here's the key:

S = Start (at (0,0))
L = Litter (at (0,2) and (2,0))
R = Reset (at (1,1))
X = Obstacle (at (1,0))
. = Empty

Step 1: Grid Parsing and State Initialization

Litter positions: (0,2) and (2,0), assign bits: (0,2)=bit 0, (2,0)=bit 1.
Bitmask at start: 11 (binary), meaning both pieces left.
Start at (0,0), energy = 4, mask = 0b11

Step 2: BFS Start

Queue State: (0,0), energy=4, mask=0b11, moves=0

Step 3: Exploring Paths Let’s show how to collect both pieces, with energy management:

First phase: Go to (0,2) to collect first litter

(0,0) → (0,1): energy 3
(0,1) → (0,2): energy 2 → Now on litter, update mask to 0b10 (only (2,0) left)
Moves so far: 2

Next, go to reset (must, to reach (2,0)):

(0,2) → (1,2): energy 1
(1,2) → (1,1): energy 0, it's a reset cell: energy restored to 4
Moves so far: 4

Finally, reach (2,0) (avoid obstacle at (1,0)):

(1,1) → (2,1): energy 3
(2,1) → (2,0): energy 2 → On litter, mask now 0b00, all collected!
Moves so far: 6

Optimal path (in terms of moves):

(0,0)→(0,1)→(0,2)→(1,2)→(1,1)→(2,1)→(2,0)
Path steps: 6 moves

Answer: The minimum number of moves required to collect all litter is 6.

This walk through highlights:

Tracking energy at each step: must reset or you run out.
Collecting litter updates the mask.
BFS ensures all possible paths are explored for shortest total moves.

Solution Implementation

1from typing import List
2from collections import deque
3
4class Solution:
5    def minMoves(self, classroom: List[str], energy: int) -> int:
6        m, n = len(classroom), len(classroom[0])  # Grid dimensions
7
8        # Map to assign an index to each lunchbox ("L")
9        lunchbox_idx = [[0] * n for _ in range(m)]
10        lunchbox_count = 0
11        start_i = start_j = 0
12
13        # Find the start position and lunchboxes
14        for i, row in enumerate(classroom):
15            for j, cell in enumerate(row):
16                if cell == "S":
17                    start_i, start_j = i, j
18                elif cell == "L":
19                    lunchbox_idx[i][j] = lunchbox_count
20                    lunchbox_count += 1
21
22        # If there are no lunchboxes, no moves are needed
23        if lunchbox_count == 0:
24            return 0
25
26        # visited[i][j][energy_left][lunchbox_mask]
27        visited = [
28            [[[False] * (1 << lunchbox_count) for _ in range(energy + 1)] for _ in range(n)]
29            for _ in range(m)
30        ]
31
32        # Initial state: start position, full energy, all lunchboxes left to collect
33        queue = deque()
34        init_mask = (1 << lunchbox_count) - 1  # All bits set: all lunchboxes uncollected
35        queue.append((start_i, start_j, energy, init_mask))
36        visited[start_i][start_j][energy][init_mask] = True
37
38        # Directions: up, right, down, left
39        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
40
41        moves = 0
42        while queue:
43            for _ in range(len(queue)):
44                x, y, curr_energy, mask = queue.popleft()
45
46                # All lunchboxes collected
47                if mask == 0:
48                    return moves
49
50                # No energy left
51                if curr_energy <= 0:
52                    continue
53
54                for dx, dy in directions:
55                    nx, ny = x + dx, y + dy
56
57                    # Check boundaries and for obstacles
58                    if 0 <= nx < m and 0 <= ny < n and classroom[nx][ny] != "X":
59                        # If on a rest tile ("R"), restore energy; otherwise, lose 1 energy
60                        next_energy = energy if classroom[nx][ny] == "R" else curr_energy - 1
61                        next_mask = mask
62                        # If on a lunchbox ("L"), mark it as collected in the mask
63                        if classroom[nx][ny] == "L":
64                            next_mask &= ~(1 << lunchbox_idx[nx][ny])
65
66                        if not visited[nx][ny][next_energy][next_mask]:
67                            visited[nx][ny][next_energy][next_mask] = True
68                            queue.append((nx, ny, next_energy, next_mask))
69            moves += 1
70
71        # Not possible to collect all lunchboxes
72        return -1
73

1class Solution {
2    public int minMoves(String[] classroom, int energy) {
3        int rows = classroom.length;
4        int cols = classroom[0].length();
5        int[][] leverIndex = new int[rows][cols]; // To store the indices of levers ('L')
6        int startX = 0, startY = 0; // Starting point
7        int leverCount = 0; // Total levers
8
9        // First pass: find the starting position and record lever positions.
10        for (int i = 0; i < rows; i++) {
11            String row = classroom[i];
12            for (int j = 0; j < cols; j++) {
13                char cell = row.charAt(j);
14                if (cell == 'S') { // Start position
15                    startX = i;
16                    startY = j;
17                } else if (cell == 'L') { // Lever
18                    leverIndex[i][j] = leverCount;
19                    leverCount++;
20                }
21            }
22        }
23
24        // If there are no levers, no moves needed.
25        if (leverCount == 0) {
26            return 0;
27        }
28
29        // vis: tracks states [row][col][current energy][bitmask lever state]
30        boolean[][][][] visited = new boolean[rows][cols][energy + 1][1 << leverCount];
31        List<int[]> queue = new ArrayList<>();
32        int allLeversMask = (1 << leverCount) - 1; // Bitmask indicating all levers yet to be triggered
33        queue.add(new int[]{startX, startY, energy, allLeversMask});
34        visited[startX][startY][energy][allLeversMask] = true;
35
36        // Directions: up, left, down, right
37        int[] directions = {-1, 0, 1, 0, -1};
38        int moves = 0;
39
40        // BFS traversal
41        while (!queue.isEmpty()) {
42            List<int[]> nextQueue = new ArrayList<>();
43            for (int[] state : queue) {
44                int x = state[0], y = state[1], currEnergy = state[2], leverMask = state[3];
45                if (leverMask == 0) { // All levers triggered
46                    return moves;
47                }
48                if (currEnergy <= 0) {
49                    continue; // Skip states with no energy
50                }
51                // Try moving to four directions
52                for (int d = 0; d < 4; d++) {
53                    int newX = x + directions[d];
54                    int newY = y + directions[d + 1];
55                    if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && classroom[newX].charAt(newY) != 'X') {
56                        // If cell is a recharger ('R'), reset energy. Otherwise, decrease energy by 1.
57                        int newEnergy = (classroom[newX].charAt(newY) == 'R') ? energy : currEnergy - 1;
58                        int newMask = leverMask;
59                        // If it's a lever ('L'), mark this lever as triggered in the mask
60                        if (classroom[newX].charAt(newY) == 'L') {
61                            newMask &= ~(1 << leverIndex[newX][newY]);
62                        }
63                        if (!visited[newX][newY][newEnergy][newMask]) {
64                            visited[newX][newY][newEnergy][newMask] = true;
65                            nextQueue.add(new int[]{newX, newY, newEnergy, newMask});
66                        }
67                    }
68                }
69            }
70            queue = nextQueue;
71            moves++; // Increase move count by 1 per BFS level
72        }
73        // No possible way to trigger all levers and finish
74        return -1;
75    }
76}
77

1#include <vector>
2#include <queue>
3#include <string>
4#include <tuple>
5
6using namespace std;
7
8class Solution {
9public:
10    // Returns the minimum number of moves to collect all 'L' seats
11    // with energy replenished on 'R' squares, obstacles are 'X'.
12    int minMoves(vector<string>& classroom, int energy) {
13        int m = classroom.size();
14        int n = classroom[0].size();
15
16        // d[i][j] gives bit position of 'L' at (i,j), or 0 otherwise
17        vector<vector<int>> l_index(m, vector<int>(n, 0));
18        int start_x = 0, start_y = 0, total_L = 0;
19
20        // Find starting point 'S' and enumerate all 'L'
21        for (int i = 0; i < m; ++i) {
22            for (int j = 0; j < n; ++j) {
23                char c = classroom[i][j];
24                if (c == 'S') {
25                    start_x = i;
26                    start_y = j;
27                } else if (c == 'L') {
28                    l_index[i][j] = total_L;
29                    total_L++;
30                }
31            }
32        }
33
34        if (total_L == 0) {
35            // No 'L' to visit, zero moves needed
36            return 0;
37        }
38
39        // visited[x][y][cur_energy][mask] indicates if (x,y) with cur_energy and mask of 'L' visited was processed
40        vector<vector<vector<vector<bool>>>> visited(
41            m, vector<vector<vector<bool>>>(n, vector<vector<bool>>(energy + 1, vector<bool>(1 << total_L, false)))
42        );
43
44        // BFS queue: x, y, current energy, L-mask (unvisited 'L' are 1 in mask)
45        queue<tuple<int, int, int, int>> q;
46        int all_unvisited_mask = (1 << total_L) - 1;
47        q.emplace(start_x, start_y, energy, all_unvisited_mask);
48        visited[start_x][start_y][energy][all_unvisited_mask] = true;
49
50        // Directions: up, right, down, left
51        const vector<int> dx = {-1, 0, 1, 0};
52        const vector<int> dy = {0, 1, 0, -1};
53
54        int moves = 0;
55
56        // Standard BFS template
57        while (!q.empty()) {
58            int level_size = q.size();
59            for (int s = 0; s < level_size; ++s) {
60                auto [x, y, cur_energy, l_mask] = q.front();
61                q.pop();
62
63                // If all 'L' have been visited (mask is 0), done
64                if (l_mask == 0) {
65                    return moves;
66                }
67                // No energy left, can't move
68                if (cur_energy <= 0) {
69                    continue;
70                }
71
72                // Explore all 4 directions
73                for (int dir = 0; dir < 4; ++dir) {
74                    int nx = x + dx[dir];
75                    int ny = y + dy[dir];
76
77                    // Continue only if within grid and not hitting an obstacle
78                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && classroom[nx][ny] != 'X') {
79                        // Replenish energy if on 'R', else use 1 energy
80                        int next_energy = classroom[nx][ny] == 'R' ? energy : cur_energy - 1;
81                        int next_mask = l_mask;
82
83                        // Update mask if this cell is 'L'
84                        if (classroom[nx][ny] == 'L') {
85                            next_mask &= ~(1 << l_index[nx][ny]);
86                        }
87
88                        if (!visited[nx][ny][next_energy][next_mask]) {
89                            visited[nx][ny][next_energy][next_mask] = true;
90                            q.emplace(nx, ny, next_energy, next_mask);
91                        }
92                    }
93                }
94            }
95            moves++;
96        }
97        // Impossible to collect all 'L's
98        return -1;
99    }
100};
101

1// Returns the minimum number of moves to collect all 'L' seats
2// with energy replenished on 'R' squares, obstacles are 'X'.
3// Uses BFS to explore all possible ways.
4function minMoves(classroom: string[], energy: number): number {
5    const m = classroom.length;
6    const n = classroom[0].length;
7
8    // lIndex[i][j] holds the bitmask position of 'L' at (i, j), or -1 if not 'L'
9    const lIndex: number[][] = Array.from({ length: m }, () => Array(n).fill(-1));
10    let startX = 0, startY = 0, totalL = 0;
11
12    // Find starting point 'S' and enumerate all 'L' seats
13    for (let i = 0; i < m; ++i) {
14        for (let j = 0; j < n; ++j) {
15            const c = classroom[i][j];
16            if (c === 'S') {
17                startX = i;
18                startY = j;
19            } else if (c === 'L') {
20                lIndex[i][j] = totalL;
21                totalL++;
22            }
23        }
24    }
25
26    if (totalL === 0) {
27        // No 'L' to collect, zero moves needed
28        return 0;
29    }
30
31    // visited[x][y][curEnergy][mask] tells if a state is already processed
32    // Dimensions: m x n x (energy+1) x (1<<totalL)
33    const visited = Array.from({ length: m }, () =>
34        Array.from({ length: n }, () =>
35            Array.from({ length: energy + 1 }, () =>
36                Array(1 << totalL).fill(false)
37            )
38        )
39    );
40
41    // BFS queue stores: [x, y, currentEnergy, LMask]
42    // LMask: Uncollected 'L's are 1 in the bitmask
43    const queue: [number, number, number, number][] = [];
44    const allUnvisitedMask = (1 << totalL) - 1;
45    queue.push([startX, startY, energy, allUnvisitedMask]);
46    visited[startX][startY][energy][allUnvisitedMask] = true;
47
48    // Directions: up, right, down, left
49    const dx = [-1, 0, 1, 0];
50    const dy = [0, 1, 0, -1];
51
52    let moves = 0;
53
54    // Standard BFS
55    while (queue.length > 0) {
56        const levelSize = queue.length;
57        for (let s = 0; s < levelSize; ++s) {
58            const [x, y, curEnergy, lMask] = queue.shift()!;
59
60            // All 'L' seats are collected
61            if (lMask === 0) {
62                return moves;
63            }
64
65            // Can't move if energy depleted
66            if (curEnergy <= 0) {
67                continue;
68            }
69
70            // Explore 4 directions
71            for (let dir = 0; dir < 4; ++dir) {
72                const nx = x + dx[dir];
73                const ny = y + dy[dir];
74
75                // If within grid and not an obstacle
76                if (
77                    nx >= 0 && nx < m &&
78                    ny >= 0 && ny < n &&
79                    classroom[nx][ny] !== 'X'
80                ) {
81                    // Replenish energy on 'R', otherwise consume one unit
82                    const nextEnergy = classroom[nx][ny] === 'R' ? energy : curEnergy - 1;
83                    let nextMask = lMask;
84
85                    // If stepping on an uncollected 'L', mark it collected in mask
86                    if (classroom[nx][ny] === 'L') {
87                        const index = lIndex[nx][ny];
88                        nextMask = nextMask & ~(1 << index);
89                    }
90
91                    // If this state not visited yet, enqueue it
92                    if (!visited[nx][ny][nextEnergy][nextMask]) {
93                        visited[nx][ny][nextEnergy][nextMask] = true;
94                        queue.push([nx, ny, nextEnergy, nextMask]);
95                    }
96                }
97            }
98        }
99        moves++;
100    }
101
102    // Impossible to collect all 'L's
103    return -1;
104}
105

Time and Space Complexity

The time complexity of the code is O(m * n * energy * 2^count), where m and n are the dimensions of the grid, energy is the initial energy, and count denotes the number of garbage ('L') cells in the classroom. This comes from the BFS processing all possible states defined by position, remaining energy, and the mask of yet-to-be-cleaned garbage.

The space complexity is also O(m * n * energy * 2^count), as the vis array stores visited states for every grid position, energy value, and garbage mask.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these properties could exist for a graph but not a tree?

Contain cycles

There are multiple ways to traverse

Connected

Has no cycle

I don't know