Minimum Moves to Clean the Classroom
MedPrompt
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'.
- Move 1: From
- 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'.
- Move 1: From
- 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 <= 201 <= n == classroom[i].length <= 20classroom[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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves exploring every possible path the student can take from the starting position. It uses a recursive (or depth-first search) strategy to navigate the grid. For every state defined by the student's position, collected litter, and current energy, it tries moving to all valid adjacent cells.
Algorithm
- Initialize a global variable
minMovesto infinity. - Identify the starting position 'S' and the locations of all 'L' litter items.
- Define a recursive function
backtrack(r, c, mask, energy, currentMoves). - Base Case: If
maskindicates all litter has been collected, updateminMoves = min(minMoves, currentMoves)and return. - Pruning: If
currentMoves >= minMoves, return, as this path cannot be better. - Recursive Step: For each of the 4 neighbors
(nr, nc): a. Check if the move is valid (in bounds, not 'X'). b. Calculate the energy after the move:newEnergy = energy - 1. c. IfnewEnergy < 0, the move is not possible. Continue. d. Determine the new masknewMaskand final energyfinalEnergybased on the cell type at(nr, nc). e. Recursively callbacktrack(nr, nc, newMask, finalEnergy, currentMoves + 1). - Start the process by calling
backtrack(startR, startC, 0, maxEnergy, 0). - After the recursion completes, if
minMovesis still infinity, it's impossible; otherwise,minMovesis the answer.
class Solution { int minMoves = Integer.MAX_VALUE; int m, n, maxEnergy, targetMask; char[][] grid; int[][] litterCoords; int[] dr = {-1, 1, 0, 0}; int[] dc = {0, 0, -1, 1}; public int minimumMoves(String[] classroom, int energy) { // ... initialization of grid, m, n, maxEnergy, litterCoords, targetMask ... // For simplicity, this part is omitted. Assume they are set up. // backtrack(startR, startC, 0, maxEnergy, 0); // return minMoves == Integer.MAX_VALUE ? -1 : minMoves; return -1; // Placeholder for full implementation } void backtrack(int r, int c, int mask, int currentEnergy, int moves) { if (moves >= minMoves) { return; } if (mask == targetMask) { minMoves = Math.min(minMoves, moves); return; } for (int i = 0; i < 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 'X') { if (currentEnergy > 0) { int nextEnergy = currentEnergy - 1; int nextMask = mask; char cell = grid[nr][nc]; if (cell == 'L') { for (int j = 0; j < litterCoords.length; j++) { if (litterCoords[j][0] == nr && litterCoords[j][1] == nc) { nextMask |= (1 << j); break; } } } else if (cell == 'R') { nextEnergy = maxEnergy; } backtrack(nr, nc, nextMask, nextEnergy, moves + 1); } } } }}Walkthrough
A recursive function, say findMinMoves(row, col, mask, energy, moves), is defined to perform the search. The state is described by the current (row, col), a bitmask mask for collected litter, the remaining energy, and the total moves taken so far.
From a given state, the function recursively calls itself for all four adjacent cells (up, down, left, right), provided the move is valid (within grid bounds, not an obstacle, and sufficient energy). When a move is made, the moves count is incremented, and energy is decremented. If the new cell contains litter, the mask is updated. If it's a reset area, energy is restored to the maximum.
A global variable, minTotalMoves, is used to keep track of the minimum moves found so far to collect all litter. Whenever a state is reached where all litter is collected (i.e., the mask is full), minTotalMoves is updated.
This method does not use memoization, meaning it may re-compute paths for the same state (row, col, mask, energy) multiple times, leading to an extremely high number of redundant calculations.
Complexity
Time
Exponential, roughly O(4^P) where P is the maximum possible path length. This is because at each step, we can branch out in up to 4 directions. This will time out on most test cases.
Space
O(P) for the recursion stack depth, where P is the maximum path length.
Trade-offs
Pros
Conceptually simple and easy to write.
Cons
Extremely inefficient due to re-computation of states.
Not feasible for the given constraints.
This approach models the problem as a variation of the Traveling Salesperson Problem (TSP). The 'cities' to visit are the starting point 'S' and all litter locations 'L'. The cost of traveling between these points is not fixed; it depends on the student's energy and the availability of reset points 'R'.
Algorithm
- Identify all Points of Interest (POIs): 'S' and all 'L's. Also, find all 'R' locations.
- Pre-computation: Run BFS from each POI and each 'R' to calculate all-pairs shortest path distances
dist(p1, p2). - Initialize a DP table
dp[k][1<<k]wherekis the number of litters.dp[i][mask]stores a pair(moves, energy). - Base Cases: For each litter
i, calculate the cost to go from 'S' toL_i(directly or via an 'R' point) and initializedp[i][1<<i]. - Iterate through
maskfrom 1 to(1<<k)-1. - For each
iwhereL_iis inmask: - For each
jwhereL_jis not inmask: a. Calculate the cost(new_moves, new_energy)to travel fromL_itoL_jstarting with energydp[i][mask].energy. b. This involves checking the direct path and all paths via reset points. c. If this new path toL_jis better than the existingdp[j][mask | (1<<j)], update it. - The result is the minimum
movesamong alldp[i][(1<<k)-1]fori=0..k-1.
class Solution { // Assuming pre-computed distances: dist[poi1_idx][poi2_idx] // Pair class for (moves, energy) class State { int moves, energy; State(int m, int e) { this.moves = m; this.energy = e; } } public int minimumMoves(String[] classroom, int energy) { // ... setup: find POIs, Rs, pre-compute distances ... int k = /* number of litters */; int numPois = k + 1; // S + L's State[][] dp = new State[k][1 << k]; // ... initialize dp table with (infinity, -1) ... // Base cases: S -> L_i for (int i = 0; i < k; i++) { // Calculate cost from S (POI 0) to L_i (POI i+1) // dp[i][1 << i] = calculateInitialState(i, energy); } for (int mask = 1; mask < (1 << k); mask++) { for (int i = 0; i < k; i++) { if ((mask & (1 << i)) != 0) { // If L_i is in mask if (dp[i][mask].moves == Integer.MAX_VALUE) continue; for (int j = 0; j < k; j++) { if ((mask & (1 << j)) == 0) { // If L_j is not in mask int nextMask = mask | (1 << j); // State state = calculateTransition(i, j, dp[i][mask], energy); // if (isBetter(state, dp[j][nextMask])) { // dp[j][nextMask] = state; // } } } } } } int minTotalMoves = Integer.MAX_VALUE; for (int i = 0; i < k; i++) { minTotalMoves = Math.min(minTotalMoves, dp[i][(1 << k) - 1].moves); } return minTotalMoves == Integer.MAX_VALUE ? -1 : minTotalMoves; }}Walkthrough
First, we pre-compute the shortest path distances (number of moves) between all pairs of important locations: 'S', all 'L's, and all 'R's. This is done by running a Breadth-First Search (BFS) from each of these locations.
Then, we use dynamic programming. The state is defined by dp[i][mask], which stores a pair (moves, energy) representing the best outcome for collecting the set of litters in mask and ending at litter i. 'Best' is defined lexicographically: we want to minimize moves, and for an equal number of moves, we want to maximize the remaining energy.
The DP transition involves iterating from a previously visited litter j (in mask) to a new litter i (not in mask). The cost of this j -> i transition is calculated by considering two possibilities:
- A direct path from
jtoi, if there's enough energy. - A path from
jtoivia the most optimal reset pointR, which minimizesdist(j, R) + dist(R, i).
The DP table is updated if a new path to (i, new_mask) is better (fewer moves, or same moves with more energy). The final answer is the minimum moves found across all final states dp[i][(1<<k)-1].
Complexity
Time
O((k + num_R) * m * n + k^2 * 2^k * num_R), where `k` is the number of litters and `num_R` is the number of reset points. The first term is for pre-computation, the second for the DP calculation. This can be slower than the full BFS if `num_R` is large.
Space
O((k + num_R) * m * n) to store the pre-computed distances. The DP table itself takes O(k * 2^k) space. This is generally much more memory-efficient than the full BFS approach.
Trade-offs
Pros
Significantly more efficient than brute-force.
Uses much less memory than a full state-space BFS.
Can be faster than BFS if the number of reset points is small.
Cons
Much more complex to implement correctly.
Performance is sensitive to the number of reset points (
num_R), and can be slow ifnum_Ris large.
This approach treats the problem as finding the shortest path in a state graph. Since each move has a uniform cost of 1, Breadth-First Search (BFS) is the ideal algorithm. The key is to define the state comprehensively to capture all necessary information for making decisions.
Algorithm
- Map each litter 'L' to a unique bit index from 0 to
k-1, wherekis the total number of litters. The target mask will be(1 << k) - 1. - Find the starting 'S' coordinates
(startR, startC). - Initialize a queue for BFS and a 4D array
dist[m][n][1<<k][energy+1]with infinity. - Set the initial state:
dist[startR][startC][0][maxEnergy] = 0and add(startR, startC, 0, maxEnergy)to the queue. - While the queue is not empty:
a. Dequeue the current state
(r, c, mask, e). b. Ifmask == targetMask, we have collected all litter. Returndist[r][c][mask][e]. c. For each of the 4 neighbors(nr, nc): i. Check if the move is valid (in bounds, not 'X', ande > 0). ii. Calculate the state after the move:newMoves = dist[r][c][mask][e] + 1,newEnergy = e - 1,newMask = mask. iii. Ifgrid[nr][nc] == 'L', updatenewMaskby setting the corresponding bit. iv. Ifgrid[nr][nc] == 'R', setnewEnergy = maxEnergy. v. IfnewMoves < dist[nr][nc][newMask][newEnergy], updatedist[nr][nc][newMask][newEnergy] = newMovesand enqueue the new state(nr, nc, newMask, newEnergy). - If the queue becomes empty and we haven't found a solution, it's impossible. Return -1.
class Solution { public int minimumMoves(String[] classroom, int energy) { int m = classroom.length; int n = classroom[0].length(); List<int[]> litters = new ArrayList<>(); int startR = -1, startC = -1; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (classroom[i].charAt(j) == 'L') { litters.add(new int[]{i, j}); } else if (classroom[i].charAt(j) == 'S') { startR = i; startC = j; } } } int k = litters.size(); if (k == 0) return 0; int targetMask = (1 << k) - 1; int[][][][] dist = new int[m][n][1 << k][energy + 1]; for (int[][][] a1 : dist) for (int[][] a2 : a1) for (int[] a3 : a2) Arrays.fill(a3, -1); Queue<int[]> queue = new LinkedList<>(); // state: {r, c, mask, energy} queue.offer(new int[]{startR, startC, 0, energy}); dist[startR][startC][0][energy] = 0; int[] dr = {-1, 1, 0, 0}; int[] dc = {0, 0, -1, 1}; while (!queue.isEmpty()) { int[] curr = queue.poll(); int r = curr[0], c = curr[1], mask = curr[2], e = curr[3]; int moves = dist[r][c][mask][e]; if (mask == targetMask) return moves; for (int i = 0; i < 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (nr >= 0 && nr < m && nc >= 0 && nc < n && classroom[nr].charAt(nc) != 'X') { if (e > 0) { int ne = e - 1; int nMask = mask; char cell = classroom[nr].charAt(nc); if (cell == 'L') { for (int j = 0; j < k; j++) { if (litters.get(j)[0] == nr && litters.get(j)[1] == nc) { nMask |= (1 << j); break; } } } if (cell == 'R') { ne = energy; } if (dist[nr][nc][nMask][ne] == -1) { dist[nr][nc][nMask][ne] = moves + 1; queue.offer(new int[]{nr, nc, nMask, ne}); } } } } } return -1; }}Walkthrough
The state in our BFS needs to track not just the student's position, but also which litter has been collected and the current energy level. Thus, a state is represented by a tuple: (row, col, mask, energy).
(row, col): The student's current coordinates.mask: A bitmask where the i-th bit is set if the i-th litter has been collected.energy: The student's current energy.
We use a queue to perform the BFS and a multi-dimensional array, dist[row][col][mask][energy], to store the minimum moves to reach each state. This dist array also serves as a visited set to prevent cycles and redundant computations.
The BFS starts with the initial state: (start_row, start_col, 0, max_energy). In each step, we dequeue a state and explore its neighbors. For each valid move, we calculate the new state (updated position, mask, and energy). If we land on a reset 'R' cell, the energy is restored to its maximum. If this new state is reached with fewer moves than recorded in dist, we update dist and enqueue the new state.
The search terminates as soon as we reach any state where all litter has been collected (i.e., mask is full). The number of moves to reach this state is the minimum possible.
Complexity
Time
O(m * n * 2^k * energy). The time complexity is proportional to the number of states, as BFS visits each state at most once. `m, n` are grid dimensions, `k` is the number of litters.
Space
O(m * n * 2^k * energy). This is dominated by the `dist` array used to store the minimum moves to each state and prevent cycles.
Trade-offs
Pros
Guaranteed to find the shortest path in terms of moves.
Conceptually straightforward application of BFS on a state graph.
More robust and often faster than the TSP DP approach for the given constraints, especially when the number of reset points is high.
Cons
High memory usage due to the large state space. Could be an issue if constraints were larger.
Solutions
Solution
class Solution {public int minMoves(String[] classroom, int energy) { int m = classroom.length, n = classroom[0].length(); int[][] d = new int[m][n]; int x = 0, y = 0, cnt = 0; for (int i = 0; i < m; i++) { String row = classroom[i]; for (int j = 0; j < n; j++) { char c = row.charAt(j); if (c == 'S') { x = i; y = j; } else if (c == 'L') { d[i][j] = cnt; cnt++; } } } if (cnt == 0) { return 0; } boolean[][][][] vis = new boolean[m][n][energy + 1][1 << cnt]; List<int[]> q = new ArrayList<>(); q.add(new int[]{x, y, energy, (1 << cnt) - 1}); vis[x][y][energy][(1 << cnt) - 1] = true; int[] dirs = {-1, 0, 1, 0, -1}; int ans = 0; while (!q.isEmpty()) { List<int[]> t = q; q = new ArrayList<>(); for (int[] state : t) { int i = state[0], j = state[1], curEnergy = state[2], mask = state[3]; if (mask == 0) { return ans; } if (curEnergy <= 0) { continue; } for (int k = 0; k < 4; k++) { int nx = i + dirs[k], ny = j + dirs[k + 1]; if (nx >= 0 && nx < m && ny >= 0 && ny < n && classroom[nx].charAt(ny) != 'X') { int nxtEnergy = classroom[nx].charAt(ny) == 'R' ? energy : curEnergy - 1; int nxtMask = mask; if (classroom[nx].charAt(ny) == 'L') { nxtMask &= ~(1 << d[nx][ny]); } if (!vis[nx][ny][nxtEnergy][nxtMask]) { vis[nx][ny][nxtEnergy][nxtMask] = true; q.add(new int[]{nx, ny, nxtEnergy, nxtMask}); } } } } ans++; } return -1; }}class Solution {public: int minMoves(vector<string> &classroom, int energy) { int m = classroom.size(), n = classroom[0].size(); vector<vector<int>> d(m, vector<int>(n, 0)); int x = 0, y = 0, cnt = 0; for (int i = 0; i < m; ++i) { string &row = classroom[i]; for (int j = 0; j < n; ++j) { char c = row[j]; if (c == 'S') { x = i; y = j; } else if (c == 'L') { d[i][j] = cnt; cnt++; } } } if (cnt == 0) { return 0; } vector<vector<vector<vector<bool>>>> vis( m, vector<vector<vector<bool>>>( n, vector<vector<bool>>(energy + 1, vector<bool>(1 << cnt, false)))); queue<tuple<int, int, int, int>> q; q.emplace(x, y, energy, (1 << cnt) - 1); vis[x][y][energy][(1 << cnt) - 1] = true; vector<int> dirs = {-1, 0, 1, 0, -1}; int ans = 0; while (!q.empty()) { int sz = q.size(); while (sz--) { auto [i, j, cur_energy, mask] = q.front(); q.pop(); if (mask == 0) { return ans; } if (cur_energy <= 0) { continue; } for (int k = 0; k < 4; ++k) { int nx = i + dirs[k], ny = j + dirs[k + 1]; if (nx >= 0 && nx < m && ny >= 0 && ny < n && classroom[nx][ny] != 'X') { int nxt_energy = classroom[nx][ny] == 'R' ? energy : cur_energy - 1; int nxt_mask = mask; if (classroom[nx][ny] == 'L') { nxt_mask &= ~(1 << d[nx][ny]); } if (!vis[nx][ny][nxt_energy][nxt_mask]) { vis[nx][ny][nxt_energy][nxt_mask] = true; q.emplace(nx, ny, nxt_energy, nxt_mask); } } } } ans++; } return -1; }};class Solution: def minMoves(self, classroom: List[str], energy: int) -> int: m, n = len(classroom), len(classroom[0]) d = [[0] * n for _ in range(m)] x = y = cnt = 0 for i, row in enumerate(classroom): for j, c in enumerate(row): if c == "S": x, y = i, j elif c == "L": d[i][j] = cnt cnt += 1 if cnt == 0: return 0 vis = [[[[False] * (1 << cnt) for _ in range(energy + 1)] for _ in range(n)] for _ in range(m)] q = [(x, y, energy, (1 << cnt) - 1)] vis[x][y][energy][(1 << cnt) - 1] = True dirs = (- 1, 0, 1, 0, - 1) ans = 0 while q: t = q q = [] for i, j, cur_energy, mask in t: if mask == 0: return ans if cur_energy <= 0: continue for k in range(4): x, y = i + dirs[k], j + dirs[k + 1] if 0 <= x < m and 0 <= y < n and classroom[x][y] != "X": nxt_energy = (energy if classroom[x][y] == "R" else cur_energy - 1) nxt_mask = mask if classroom[x][y] == "L": nxt_mask &= ~ (1 << d[x][y]) if not vis[x][y][nxt_energy][nxt_mask]: vis[x][y][nxt_energy][nxt_mask] = True q . append((x, y, nxt_energy, nxt_mask)) ans += 1 return - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.