3568. Minimum Moves to Clean the Classroom
Difficulty: Hard | Published on 2026-09-01
This one is meaningfully harder than the previous problems — it introduces two new big ideas (BFS and bitmasks) — so let's build up carefully, same structure as before.
1. Problem in Very Simple Language
You're in a classroom represented as a grid of rows and columns. Each cell is one of:
INLINECODE0 — where the student starts (exactly one of these). INLINECODE1 — a piece of litter that must be picked up (there are at most 10 of these). INLINECODE2 — a "recharge station." Stepping on it fully restores the student's energy, no matter how little energy they had left. INLINECODE3 — a wall/obstacle. The student can never step here. INLINECODE4 — just empty floor, walk through freely.
The student also has a maximum energy capacity, INLINECODE5, and starts completely full. Every single step (up/down/left/right to a neighboring cell) costs exactly 1 energy. If energy would hit 0 and the student isn't standing on an INLINECODE6, they're stuck — they cannot take another step unless they're on a reset tile.
Goal: find the minimum total number of moves needed to walk over every INLINECODE7 cell at least once (collecting all litter), or return INLINECODE8 if it's impossible no matter what path is taken.
What's given: the grid, and the energy capacity. What to find: the shortest walking path (respecting obstacles and the energy/recharge rule) that touches every litter cell. What to return: the number of moves in that shortest path, or INLINECODE9.
2. Real-Life Analogy
Imagine a robot vacuum with a battery that only lasts, say, 20 minutes of driving. Scattered around the house are 10 dirty spots it must visit, some walls it can't drive through, and a few charging pads that instantly top the battery back to full the moment it drives over one — no matter how low the battery was.
The robot needs to plan a route that hits all 10 dirty spots, is allowed to swing by charging pads as many times as it likes along the way, but can never let the battery hit zero anywhere except while standing on a charging pad. You want the shortest possible total driving time (in minutes) that gets every spot cleaned.
3. Important Programming Concepts I Need First
Grid / 2D Array
Concept: A grid is just a 2D array — rows and columns of cells, each reachable by INLINECODE10. Why we need it: The classroom itself is the input, given as an array of strings (each string is one row).Queue (new!)
Concept: A queue is a "first in, first out" (FIFO) structure — like a line at a coffee shop: whoever joined the line first gets served first. You add items at the back (INLINECODE11/INLINECODE12) and remove items from the front (INLINECODE13/INLINECODE14). Simple Example: Add INLINECODE15, then INLINECODE16, then INLINECODE17 → the queue is INLINECODE18 → removing gives you INLINECODE19 first, then INLINECODE20, then INLINECODE21. Why we need it: We're about to use BFS (below), and BFS always uses a queue to control the order in which we explore things.Breadth-First Search (BFS) (new — the central idea of this problem!)
Concept: BFS is a way to explore a graph (or grid) "layer by layer" — first you look at everything reachable in 1 step, then everything reachable in exactly 2 steps, then 3, and so on. Because it expands in complete layers, the very first time BFS reaches some target, that's guaranteed to be via the shortest possible number of steps. This makes BFS the standard tool whenever a problem asks for a minimum number of moves/steps on a grid, with all moves costing the same (1 each). Simple Example: Starting at a cell, BFS visits all 4 direct neighbors first (distance 1), then all cells reachable from those (distance 2), etc., never revisiting a cell once it's been reached. Why we need it: The entire problem is "minimum number of moves" — a textbook signal for BFS.State (a very important concept for this problem)
Concept: Normally in a grid BFS, "where you are" (just row, column) is enough information to know what you can do next. But here, two students standing on the exact same cell might be able to do very different things depending on how much energy they have left and which litter they've already picked up — so "state" here must include more than position. A state is simply "all the information needed to know exactly what happens next." Why we need it: This problem's state is INLINECODE22 — not just INLINECODE23.Bitmask (new!)
Concept: A bitmask is a compact way to represent "which items from a small set have been chosen," using the binary digits (bits) of a single number. If you have up to 10 litter items, number them INLINECODE24 through INLINECODE25. A number's bit at position INLINECODE26 being INLINECODE27 means "litter item INLINECODE28 has been collected"; INLINECODE29 means "not yet." For example, if litter items INLINECODE30 and INLINECODE31 are collected but not INLINECODE32, the mask in binary is INLINECODE33, which is the number INLINECODE34. Simple Example: With 3 litter items, INLINECODE35 means "none collected," INLINECODE36 (binary INLINECODE37) means "all 3 collected." Checking bit INLINECODE38: INLINECODE39. Setting bit INLINECODE40: INLINECODE41. Why we need it: Since there are at most 10 litter pieces, there are at most INLINECODE42 possible "which ones are collected" combinations — small enough to treat as just another number in our state, instead of tracking a whole separate list/set.4-directional movement
Concept: From any cell INLINECODE43, the 4 neighbors are INLINECODE44 up, INLINECODE45 down, INLINECODE46 left, INLINECODE47 right. Why we need it: Every move in this problem is exactly one of these 4 steps.Array (multi-dimensional, for tracking "have I already visited this exact state?")
Concept: Just like a 1D array has one index, we can have arrays indexed by multiple things at once (conceptually a 4D array here: row, column, energy, mask). Why we need it: BFS needs to avoid revisiting the exact same state twice (otherwise it could loop forever or waste huge amounts of time) — we need a fast way to check "have I been in this exact (position, energy, collected-so-far) situation before?"4. Understand the Input
Take Example 2: CODEBLOCK0
This is a 2-row, 2-column grid:
| col 0 | col 1 | |
|---|---|---|
| row 0 | INLINECODE48 | INLINECODE49 |
| row 1 | INLINECODE50 | INLINECODE51 |
5. Understand the Output
Output: INLINECODE62
Path: INLINECODE63 [collect litter #1, energy: 4→3] → INLINECODE64 [step on R, energy resets to 4] → INLINECODE65 [collect litter #2, energy: 4→3]. That's 3 total moves, and litter is fully collected. There's no way to do it in fewer moves (you need at least 1 move to reach each litter cell from a shared adjacent cell, and here neither litter cell is adjacent to the other, so at least 3 moves are structurally required, and 3 is achievable) — so INLINECODE66 is optimal. Notice the recharge wasn't even strictly needed for the energy here (energy stayed positive throughout even without it) — it's just naturally on the shortest path between the two litter pieces. In harder cases, you'd be forced through an INLINECODE67 purely to survive long stretches without running out of energy.
6. Solve the Example Manually
Let's manually reason through Example 3, since it's the trickiest (INLINECODE68 case):
CODEBLOCK1
Grid:
| col 0 | col 1 | col 2 | |
|---|---|---|---|
| row 0 | INLINECODE69 | INLINECODE70 | INLINECODE71 |
| row 1 | INLINECODE72 | INLINECODE73 | INLINECODE74 |
Let's see what's reachable: From INLINECODE77, moves left to INLINECODE78 [energy 3→2], then INLINECODE79 [energy 2→1] — that's litter #1 collected, using 2 moves, energy left = 1. From INLINECODE80, energy is 1. Can we get to INLINECODE81 (the INLINECODE82)? Yes — that's adjacent, 1 move, energy would hit 0 upon arrival, but since INLINECODE83 is INLINECODE84, energy resets to full (3) the instant we land there. Now from INLINECODE85 with energy 3 (freshly reset), we need to reach INLINECODE86 (litter #2). But INLINECODE87 is INLINECODE88 — a wall! We cannot go directly right. Is there any other route from INLINECODE89 to INLINECODE90? Going back up to INLINECODE91 → INLINECODE92 → INLINECODE93 → down to INLINECODE94... let's check: INLINECODE95 [1 move] INLINECODE96 [1] INLINECODE97 [1] INLINECODE98 [1] = 4 moves, but we only have 3 energy after the reset, and no INLINECODE99 along this new sub-route. We run out of energy exactly at INLINECODE100 (having used all 3), unable to take the 4th move down to INLINECODE101. Is there any other path to INLINECODE102 at all? The only way into INLINECODE103 is from INLINECODE104 (above) or INLINECODE105 (blocked by INLINECODE106). And reaching INLINECODE107 from anywhere requires passing through the top row, which (from the INLINECODE108 at INLINECODE109) costs at least 3 moves just to reach INLINECODE110, leaving 0 energy — not enough for the 4th move into INLINECODE111. No matter how we shuffle the order, litter cell INLINECODE112 is simply unreachable within the energy budget. So the answer is INLINECODE113. ✔️ matches!
This example really shows why we can't just think "shortest path ignoring energy" — the energy budget can make an otherwise-reachable cell permanently unreachable.
7. Think Like a Programmer
What do I know? The grid layout, where obstacles/recharges/litter are, and the energy cap. What do I need to find? The minimum moves to touch all litter cells, respecting the energy rule. What can I try? Since "minimum moves on a grid" is the classic signal for BFS, my first instinct is BFS. But normal grid BFS only tracks position — here I also need to know how much energy I have left (since that affects what moves are even legal) AND which litter I've already picked up (since I need ALL of it, not just any one piece). What happens if I try every possibility? If I tried every possible order of visiting the 10 litter pieces (10! ≈ 3.6 million orderings) and, for each order, tried to find full paths between them, that's technically finite, but doesn't cleanly account for energy carrying over between litter pickups (energy left when you finish leg 1 affects what's affordable on leg 2) — this naive ordering approach gets complicated fast and doesn't obviously give minimum moves easily. Can I make it faster / cleaner? Yes — bundle everything relevant into a single BFS state: INLINECODE114. Now a single BFS, expanding one state at a time, naturally handles "try every order," "track energy correctly across the whole journey (including resets)," and "know exactly when we're fully done (mask is complete)" — all at once, and BFS guarantees the first time we reach a "mask is complete" state is via the minimum number of moves. What information should I remember? For every combination of (cell, energy level, litter collected so far), have I already visited it? If yes, skip it (no point re-exploring identical situations). What pattern do I notice? This is a "shortest path in an enlarged graph" — the "nodes" of our graph aren't just grid cells, they're INLINECODE115 triples. Once you see it this way, it's just ordinary BFS on a bigger graph.
8. Start With the Brute Force Solution
Here, "brute force" and "correct optimized approach" are actually the same core idea — full-state BFS — because trying to shortcut it (e.g., ignoring energy, or ignoring litter-order) produces wrong answers, not just slow ones. So let's build the full-state BFS directly, understanding why each piece of the state is necessary, rather than starting from something naively wrong.
Why full-state BFS works: Every legal sequence of moves corresponds to some walk through these INLINECODE116 states. BFS explores all such walks in order of increasing move-count, so the first time it finds any state where INLINECODE117 equals "everything collected," that's provably the minimum possible number of moves.
Time complexity: Number of distinct states ≤ INLINECODE118. With the given limits (INLINECODE119, INLINECODE120, INLINECODE121), that's at most INLINECODE122 states, each with 4 possible moves — a large but finite and manageable amount of work for a computer.
Space complexity: We need to remember whether each of those ~20.9 million states has been visited — an array of that size.
9. Explain the Core Idea Piece by Piece
Before jumping to code, let's make sure each part of the state makes sense:
Why include INLINECODE123? Obviously — we need to know where the student physically is, to know which moves are legal (not into a wall, not off the grid). Why include INLINECODE124? Because the same cell can be in two very different "situations" depending on how much energy is left — with 5 energy left you might be able to reach a far-away litter cell directly, but with 1 energy left from that same cell, you might need to detour through a recharge station first. Two students on the same cell with different energy can have completely different futures — so energy must be part of the state, not just a side detail. Why include the litter bitmask? Because we need to know the goal condition: "have we collected everything?" A student standing on a specific cell having collected litter INLINECODE125 versus having collected INLINECODE126 are in genuinely different situations for the rest of the problem (different amounts of remaining work) — bundling this into the state lets BFS naturally explore "all possible orders" of collection without us having to code that separately. What happens when we step onto an INLINECODE127 cell? Regardless of what our energy was before the move, the moment we land on INLINECODE128, energy becomes full again. This is a simple rule to encode: INLINECODE129. What happens when we step onto an INLINECODE130 cell? We simply turn on that litter's bit in the mask: INLINECODE131. (Stepping on an already-collected litter cell again just leaves the bit already-on — no harm, no special case needed.) When can we NOT move at all? If current energy is INLINECODE132 and we're not on an INLINECODE133 (but remember: if we're currently on INLINECODE134, our energy in the state is already full, since we reset it the instant we arrived — so energy being INLINECODE135 in our state representation always means "genuinely stuck," never "on a recharge tile with 0 shown").
11. From Idea to Algorithm
CODEBLOCK2
⭐ Key Insight
Before the insight
It's tempting to think of this as "find shortest path to each litter piece separately, then combine," treating energy resets as something to handle per-leg.The problem
Energy does not reset between litter pickups — only when you physically step on an INLINECODE136 tile. So how much energy you have left when you start trying to reach the next litter piece depends entirely on your whole journey so far, not just "which litter is next." Treating legs independently (assuming full energy at the start of each leg) silently gives wrong answers whenever a path needs to arrive at a litter cell with some energy still in reserve to continue onward, or conversely, a path only barely limps to a litter cell with 0 energy left and must detour to a recharge before doing anything else.The insight
Fold energy and "litter collected so far" directly into the definition of a BFS node. Once you do that, there's no more separate bookkeeping needed for orderings or energy resets — plain BFS, expanding one move at a time, automatically discovers the correct minimum-move journey through any order of litter and any number of recharges, because it's exploring the true space of possible situations, not a simplified (and subtly incorrect) approximation of it.After the insight
The "hard" combinatorial parts of this problem (which order to visit litter in, when to detour for a recharge) are never explicitly coded at all — they fall out for free from letting BFS explore the full, correctly-defined state graph.13. Dry Run (Conceptual) on Example 1
CODEBLOCK3
Grid:
| col 0 | col 1 | |
|---|---|---|
| row 0 | INLINECODE137 | INLINECODE138 |
| row 1 | INLINECODE139 | INLINECODE140 |
| Move | From state | To state | Distance |
|---|---|---|---|
| 1 | (0,0,e=2,mask=0) | (0,1,e=1,mask=0) [moved right; INLINECODE143 is INLINECODE144] | 1 |
| 2 | (0,1,e=1,mask=0) | (1,1,e=0,mask=1) [moved down; INLINECODE145 is INLINECODE146, so bit 0 turns on] | 2 |
14. Optimized Code
CODEBLOCK4
CODEBLOCK5
15. Explain the Code Line by Line
INLINECODE150 — convert the array of strings into a 2D character grid, so we can index INLINECODE151 directly. The first double loop — scans every cell once to find the single INLINECODE152 (recording INLINECODE153) and to assign each INLINECODE154 cell a unique bit index (INLINECODE155), stored in INLINECODE156. Any cell that isn't litter keeps INLINECODE157 in INLINECODE158. INLINECODE159 — this produces a number whose lowest INLINECODE160 bits are all INLINECODE161 — e.g., with 3 litter pieces, INLINECODE162. This is our "everything collected" target. INLINECODE163 — an edge case: if there's no litter at all, we're already done with zero moves. INLINECODE164 — this is our giant "have I been in this exact INLINECODE165 situation before?" tracker, flattened into a single 1D array for speed (Java doesn't handle huge multi-dimensional arrays as efficiently as one big 1D array with manual index math). INLINECODE166 — converts a INLINECODE167 combination into one unique integer index into that flat INLINECODE168 array, similar to how you'd convert a 2D grid position into a 1D array index (INLINECODE169), just extended with two more "digits" (INLINECODE170 and INLINECODE171). INLINECODE172 — our BFS queue. Each entry stores INLINECODE173 bundled together. We seed the queue with the starting state: student's start position, full energy, empty mask, distance INLINECODE174. We also immediately mark it visited. The main INLINECODE175 loop — this is the heart of BFS: keep pulling the oldest item off the front of the queue (guaranteed by the queue's FIFO behavior to be processed in increasing distance order) and process it. INLINECODE176 — the moment we pop a state where everything's been collected, we're done — and because BFS processes states in non-decreasing distance order, this is guaranteed to be the minimum possible distance. INLINECODE177 — if there's no energy left, this state is a dead end; we don't try to generate any moves from it. The INLINECODE178 loop — tries each of the 4 directions. Boundary and obstacle checks — skip anything off the grid or blocked by INLINECODE179. INLINECODE180 — implements the recharge rule exactly as discussed: full reset if stepping onto INLINECODE181, otherwise spend 1 energy. INLINECODE182 update — if the target cell is litter, turn on its bit; otherwise the mask is unchanged. We compute the new state's flat index, and if it's never been visited, we mark it visited and add it to the queue with INLINECODE183. If the queue empties out completely without ever hitting INLINECODE184, we INLINECODE185 — meaning it's truly impossible.16. Test With Multiple Examples
Example 1 — Normal Case
INLINECODE186 → dry-ran in Section 13 → Output: INLINECODE187 ✔️Example 2 — Different Case
INLINECODE188 → BFS explores from INLINECODE189; shortest path to collecting both litter bits is 3 moves (INLINECODE190, mask becomes complete exactly when the litter at INLINECODE191 is stepped on) → Output: INLINECODE192 ✔️Example 3 — Edge Case
INLINECODE193 (as reasoned by hand in Section 6) → the state INLINECODE194 with the second litter bit set is never generated by BFS, no matter the energy value, because every route into INLINECODE195 requires more consecutive moves than any reachable energy level allows → Output: INLINECODE196 ✔️17. Edge Cases
No litter at all (INLINECODE197) → answer is immediately INLINECODE198; handled by an early return before BFS even starts. A litter cell is fully walled off (surrounded by INLINECODE199 with no path in) → BFS simply never reaches any state containing that cell, so INLINECODE200 is never achieved → INLINECODE201. Energy exactly enough, no slack at all → still works correctly, since BFS only ever generates a move when INLINECODE202 at the moment of the move, so it naturally respects "just barely enough energy" paths without any special-casing. Multiple recharge stations, and a path that needs several of them in sequence → handled naturally, since every time we land on INLINECODE203 in the BFS transition, energy resets, no matter how many times this has already happened along the path. Only 1 litter piece and it's directly reachable with no recharge needed → works like a normal single-target BFS, degrading gracefully. The grid is 1 row or 1 column → no special handling needed; the same 4-direction logic just has fewer valid moves in practice (moves off the single row/column are rejected by the boundary check).
18. Time Complexity
What is time complexity? It estimates how much work grows as inputs grow — the same "twice the input, roughly twice (or more) the work" idea as before, just now applied to a state space instead of a plain array.
CODEBLOCK6
Why: Every state is visited (and its 4 neighbors examined) at most once, thanks to the INLINECODE204 array preventing re-processing. So the total work is proportional to the total number of possible states, times a small constant (4 directions). With the problem's guaranteed small limits (INLINECODE205, INLINECODE206, INLINECODE207), this comes out to roughly 20 million states — large, but a fixed, bounded amount of work a computer can chew through, unlike something that grows explosively (like trying every possible order of visiting 10 litter pieces, which would be INLINECODE208 million orderings, each potentially requiring its own separate search — the state-based BFS elegantly avoids needing to enumerate orderings at all).
19. Space Complexity
The INLINECODE209 boolean array has one entry per possible state: INLINECODE210 — up to about 20.9 million INLINECODE211 entries. The BFS queue, at any moment, holds a subset of these states (bounded by the same total).
So overall extra space is INLINECODE212 — the same bound as the time complexity, since we need to remember every state we might visit.
20. Common Mistakes Beginners Make
❌ "I'll just do BFS on INLINECODE213 only, like a normal shortest-path grid problem." ✅ Plain INLINECODE214 BFS can't tell the difference between "I'm here with lots of energy" and "I'm here with almost none," nor can it know which litter has already been collected — both are essential to correctness here, not just optimizations.
❌ "I'll compute shortest distances between each pair of key points (S and each L) separately, assuming full energy at the start of each leg, then combine them like a traveling-salesman problem." ✅ This silently assumes energy resets between litter pickups, which isn't true — energy only resets at INLINECODE215 tiles. This approach can give wrong (too optimistic or too pessimistic) answers, as shown conceptually in Section 8's introduction.
❌ "If energy hits exactly 0, but I'm about to arrive at an INLINECODE216 cell, that's not allowed." ✅ It's allowed — the check is about whether you have energy before making a move (INLINECODE217 to attempt any move at all), and if the destination of that move is INLINECODE218, the energy resets to full immediately upon arrival, regardless of how little was left just before the move.
❌ "I only need to mark a cell as visited once, regardless of energy or mask." ✅ You must track visited status per entire state INLINECODE219 — the same cell can legitimately be revisited many times throughout a solution, as long as it's with a genuinely new energy level or litter combination not seen before at that cell.
❌ "Since there could be up to 10 litter pieces, I should try all INLINECODE220 orderings explicitly." ✅ Unnecessary — folding the collected-litter bitmask into the BFS state already implicitly explores every meaningful ordering, without you ever having to generate permutations by hand.
21. How to Recognize This Pattern in Other Problems
Watch for these signal phrases:
CODEBLOCK7
Whenever a shortest-path problem has some extra resource (energy, keys, fuel) that changes what moves are legal, and/or a small set of "must-visit" items, think: expand the BFS state to include that resource and/or a bitmask of progress, rather than trying to handle it as a separate calculation layered on top of plain positional BFS.
22. Interview Thinking
CODEBLOCK8
Applied here: the real "aha" isn't a clever formula — it's recognizing that the state itself was too small, and the fix is enlarging what a BFS "node" represents until it captures everything that actually affects the future.
23. Mini Challenge
Try these before checking the answers:
1. Why can't we just track INLINECODE221 and separately remember "current energy" and "mask" as plain variables outside the BFS state, updating them as we go? 2. If a cell has already been visited with INLINECODE222, and later BFS reaches the same cell with INLINECODE223, should we explore from this new state too, or skip it? Why? 3. Why is it fine to stop and return the answer the moment we pop a state with the full mask, instead of continuing to check if some other completion is even shorter?
Answer to Mini Challenge
1. Because BFS naturally explores many different paths at once, branching in all directions — there isn't just one single "current" energy or mask at any moment; different branches of the search are simultaneously at different cells with different energy/mask combinations. The state must travel with each branch, which is exactly what bundling it into the queue entries accomplishes. 2. We should explore it — INLINECODE224 is a genuinely different state from INLINECODE225 at the same cell, since with less energy remaining, different future moves may or may not be affordable. It's not automatically "worse" in a way that lets us skip it — treating it as unvisited is required for correctness (although as noted in Section 19, this is exactly why the state space includes the energy dimension explicitly, rather than just row/col). 3. Because BFS explores states in strictly non-decreasing order of distance (it processes everything at distance INLINECODE226 before anything at distance INLINECODE227), the very first time we encounter a "fully collected" state is guaranteed to have the smallest possible distance — no other completion, found later in the queue, could ever have a smaller distance than one found earlier.
24. Final Revision
🧠 Problem in One Sentence
Find the minimum number of grid moves to collect all litter, where energy depletes with each move and only fully resets when standing on a recharge tile.🔑 Main Idea
Treat INLINECODE228 as a single BFS state, and run ordinary breadth-first search over this enlarged state space — the first time the mask becomes "everything collected" gives the minimum moves.⚙️ Algorithm
1. Locate the start cell and assign each litter cell a unique bit. 2. BFS from INLINECODE229, exploring 4 directions per state. 3. On each move: energy resets to full if landing on INLINECODE230, otherwise drops by 1; mask gains a bit if landing on unlit litter. 4. Skip moves where current energy is 0, and skip states already visited. 5. Return the distance the instant a state with the full mask is popped; if BFS exhausts without that, return INLINECODE231.⏱️ Complexity
Time: INLINECODE232 Space: INLINECODE233🎯 Pattern to Remember
When a grid shortest-path problem has an extra depletable/resettable resource and a small "must-collect-all" set, enlarge the BFS state to INLINECODE234 rather than trying to bolt these on separately.25. Beginner Quiz
1. (Understanding) Why does energy need to be part of the BFS state instead of just checked as a side condition? 2. (Basic concept) If there are 4 litter pieces and you've collected the 2nd and 4th (using 0-indexed positions 0,1,2,3), what is the mask in binary, and as a decimal number? 3. (Logic) Why can't we safely assume energy resets to full every time we start heading toward the next litter piece? 4. (Dry run) For a tiny 1×3 grid INLINECODE235 written as a single row INLINECODE236 with INLINECODE237, walk through what BFS would do, and give the final answer. 5. (Complexity/pattern) Why does this problem's state space multiply INLINECODE238 instead of just INLINECODE239, and what specific phrase in the problem (about energy resetting) is the clue that a plain positional BFS would be incorrect, not just slow?