Minimum Moves to Collect Classroom Litter
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Minimum Moves to Collect Classroom Litter
You are given a rectangular grid `classroom` and a positive integer `energy`. The grid contains:
- `S`: the starting cell, where you begin with `energy` units available.
- `L`: one piece of litter. Entering the cell collects it; that cell is empty afterward.
- `R`: a reusable reset cell that restores energy to the full capacity `energy`.
- `X`: an impassable obstacle.
- `.`: an empty cell.
Each move goes one cell up, down, left, or right and costs one unit of energy. Entering an `R` cell restores full energy, including when the move used the last available unit. With zero energy on a non-reset cell, you cannot make another move.
Return the minimum number of moves needed to collect every piece of litter, or `-1` if this is impossible. You may finish as soon as the final piece is collected; returning to the start is not required.
### C++ Interface
```cpp
class Solution {
public:
int minMoves(vector<string>& classroom, int energy);
};
```
### Examples
**Example 1**
```text
classroom = ["S.R.L"]
energy = 2
Output: 4
```
Move right four times. After two moves you reach the reset cell with zero energy and immediately refill to two. Two more moves collect the litter, again with zero energy left. The litter is four cells from the start, so fewer than four moves cannot reach it.
**Example 2**
```text
classroom = ["S.LL"]
energy = 2
Output: -1
```
Reaching the first litter uses both energy units. There is no reset cell, so the next litter cannot be reached. No detour can provide additional energy.
### Constraints
- `1 <= classroom.length <= 20`.
- `1 <= classroom[i].length <= 20`; all rows have the same length.
- Cells contain only `S`, `L`, `R`, `X`, or `.`.
- There is exactly one `S` and at most ten `L` cells.
- `1 <= energy <= 50`.
### Clarifying Questions
- Can reset cells be used repeatedly? Yes. Every visit restores full capacity.
- Is a litter item collected again on a later visit? No. Each item is collected only once.
- May the last litter be collected using the final energy unit? Yes. No further move is needed after all items are collected.
- What if there are no litter cells? The answer is zero.
- Does returning to `S` recharge energy? No. Only `R` cells provide resets.
### What a Strong Answer Covers
- Exact movement costs, obstacle handling, and reusable energy resets.
- Collection of every litter item once, including revisits to previously collected cells.
- The minimum valid move count, or a justified impossibility result.
- Resource bounds for a grid up to 20 by 20, ten litter items, and energy capacity up to fifty.
### Follow-up Questions
- Why can a route be complete with zero remaining energy even though further movement would be impossible?
- Can visiting the same reset cell more than once be useful under the stated rules?
```hint Describe the complete situation
Use breadth-first search over the current cell, the set of collected litter items, and remaining energy. A move decreases energy, then applies the destination's collection or reset effect. Different energy levels at the same cell with the same collected set are distinct search states.
```
Overview: Find the fewest grid moves needed to collect every litter item while spending energy and using reusable reset cells. Respect obstacles, allow a zero-energy finish, and report impossible routes.
