Difficulty: 🟡 Medium
Topics: Array, Hash Table, Bit Manipulation, Breadth-First Search, Matrix

Solution

LeetCode 3568 - Minimum Moves to Clean the Classroom

Problem Understanding

We are given a grid representing a classroom. A student starts at the cell marked 'S' and must collect every litter cell marked 'L'. Movement is allowed only in the four cardinal directions, and moving one cell costs exactly one unit of energy.

The student begins with a maximum energy value energy. Every move decreases the current energy by one. When the student steps onto a reset cell 'R', their energy is immediately restored back to the maximum capacity. Reset cells may be used any number of times.

Obstacle cells 'X' cannot be entered. Empty cells '.' are traversable but have no special effect.

The goal is to determine the minimum number of moves required to collect all litter cells. If no valid sequence of moves can collect every litter item, we return -1.

The key challenge is that the state of the search is not determined only by position. The current energy level matters because it restricts future movement. Additionally, the set of litter already collected matters because collecting all litter is the objective.

The constraints provide important clues:

The grid size is at most 20 × 20, so there are at most 400 cells.
Energy is at most 50.
There are at most 10 litter cells.

The small limit on litter count strongly suggests using bitmasking. A bitmask with 10 bits can represent every possible subset of collected litter. Since we need the minimum number of moves, a shortest-path search such as Breadth-First Search is a natural candidate.

Several edge cases are worth noting:

Some litter may be unreachable because of obstacles.
Energy may be insufficient to reach a litter unless a reset station is visited.
A path may require revisiting cells multiple times.
There may be no litter at all, in which case the answer is 0.
Reaching energy 0 is only useful if the student is standing on a reset cell, because otherwise no further move can be made.

Approaches

Brute Force

A brute-force solution would attempt to enumerate all possible movement sequences. Starting from the initial position, it would recursively explore every valid move, track the remaining energy, update collected litter, and search for a sequence that collects everything.

This approach is correct because it eventually explores every possible valid path. However, it is completely impractical. The number of possible movement sequences grows exponentially with path length. Even a modest grid can produce an enormous search space.

Since the shortest path is required, we would still need to examine many states before proving optimality. The state space includes position, energy level, and collected litter status, making naive exhaustive search infeasible.

Key Insight

This is fundamentally a shortest-path problem on an expanded state graph.

A state is defined by:

Current row
Current column
Current remaining energy
Bitmask of collected litter

From any state, we can move to neighboring cells if:

The destination is inside the grid
The destination is not an obstacle
We have enough energy to make the move

Every move costs exactly one step, which means Breadth-First Search will naturally discover the minimum number of moves.

The important observation is that although the grid contains up to 400 cells, the litter count is at most 10. Therefore the bitmask dimension has at most 2^10 = 1024 possibilities, which is manageable.

We simply perform BFS over the expanded state space and stop when the litter bitmask indicates that all litter has been collected.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all possible movement sequences
Optimal BFS with State Compression	O(m × n × energy × 2^L)	O(m × n × energy × 2^L)	BFS over position, energy, and collected-litter mask

Here L is the number of litter cells and L ≤ 10.

Algorithm Walkthrough

Step 1: Parse the Grid

Scan the entire grid.

Record:

The starting position 'S'
Every litter position 'L'

Assign each litter cell a unique index from 0 to L - 1.

These indices will correspond to bits in the collection mask.

Step 2: Create the Target Mask

If there are L litter cells, then:

targetMask = (1 << L) - 1

When the current mask equals targetMask, every litter has been collected.

Step 3: Build the Initial BFS State

The starting state consists of:

Start row
Start column
Full energy
Empty litter mask

The initial distance is 0 moves.

Step 4: Maintain a Visited Structure

A state is uniquely identified by:

(row, col, remainingEnergy, litterMask)

Revisiting an identical state can never improve the answer because BFS already reached it with the minimum number of moves.

Therefore each state is processed at most once.

Step 5: Perform Breadth-First Search

Repeatedly remove the front state from the queue.

If its litter mask equals the target mask, return the current distance.

Otherwise explore all four neighboring cells.

Step 6: Validate Movement

For each neighbor:

Check grid bounds.
Skip obstacles 'X'.
Ensure current energy is at least 1.

Moving consumes one energy point.

newEnergy = currentEnergy - 1

Step 7: Apply Reset Cells

After arriving at the new cell:

If it is 'R', restore energy to maximum.

newEnergy = energy

Step 8: Update Litter Mask

If the new cell contains litter:

Determine its assigned index.
Set the corresponding bit.

newMask |= (1 << litterIndex)

Step 9: Push Unvisited States

If the resulting state has not been seen before:

Mark it visited.
Add it to the queue with distance + 1.

Step 10: Handle Failure

If BFS finishes without reaching the target mask, return -1.

Why it works

Breadth-First Search explores states in nondecreasing order of move count. Every transition corresponds to exactly one move, so the first time BFS reaches a state where all litter has been collected, that state represents the minimum possible number of moves.

The state representation captures all information that affects future decisions: current location, remaining energy, and collected litter. Therefore two identical states are equivalent, and skipping revisits cannot eliminate an optimal solution. This guarantees correctness.

Python Solution

from collections import deque
from typing import List

class Solution:
    def minMoves(self, classroom: List[str], energy: int) -> int:
        m, n = len(classroom), len(classroom[0])

        start_r = start_c = -1
        litter_index = {}
        litter_count = 0

        for r in range(m):
            for c in range(n):
                cell = classroom[r][c]

                if cell == 'S':
                    start_r, start_c = r, c
                elif cell == 'L':
                    litter_index[(r, c)] = litter_count
                    litter_count += 1

        if litter_count == 0:
            return 0

        target_mask = (1 << litter_count) - 1

        start_state = (start_r, start_c, energy, 0)

        queue = deque([(start_r, start_c, energy, 0, 0)])
        visited = {start_state}

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while queue:
            r, c, curr_energy, mask, moves = queue.popleft()

            if mask == target_mask:
                return moves

            if curr_energy == 0:
                continue

            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                if not (0 <= nr < m and 0 <= nc < n):
                    continue

                cell = classroom[nr][nc]

                if cell == 'X':
                    continue

                next_energy = curr_energy - 1

                if cell == 'R':
                    next_energy = energy

                next_mask = mask

                if cell == 'L':
                    next_mask |= 1 << litter_index[(nr, nc)]

                state = (nr, nc, next_energy, next_mask)

                if state in visited:
                    continue

                visited.add(state)
                queue.append(
                    (nr, nc, next_energy, next_mask, moves + 1)
                )

        return -1

The implementation begins by locating the start position and assigning each litter cell a unique bit index. This allows the collected litter set to be represented compactly using a bitmask.

The BFS queue stores five values:

Current row
Current column
Remaining energy
Collected-litter mask
Distance in moves

Whenever a move is made, energy decreases by one. If the destination is a reset cell, the energy is immediately restored to the maximum value. If the destination contains litter, the corresponding bit is set in the mask.

The visited set prevents processing identical states more than once. Since BFS explores states in increasing order of distance, the first time we reach the mask containing all litter is guaranteed to be optimal.

Go Solution

package main

import "container/list"

func minMoves(classroom []string, energy int) int {
	m := len(classroom)
	n := len(classroom[0])

	startR, startC := -1, -1

	type Pos struct {
		r int
		c int
	}

	litterIndex := make(map[Pos]int)
	litterCount := 0

	for r := 0; r < m; r++ {
		for c := 0; c < n; c++ {
			ch := classroom[r][c]

			if ch == 'S' {
				startR, startC = r, c
			} else if ch == 'L' {
				litterIndex[Pos{r, c}] = litterCount
				litterCount++
			}
		}
	}

	if litterCount == 0 {
		return 0
	}

	targetMask := (1 << litterCount) - 1

	type State struct {
		r      int
		c      int
		energy int
		mask   int
		dist   int
	}

	type VisitKey struct {
		r      int
		c      int
		energy int
		mask   int
	}

	queue := list.New()

	startState := State{
		r:      startR,
		c:      startC,
		energy: energy,
		mask:   0,
		dist:   0,
	}

	queue.PushBack(startState)

	visited := make(map[VisitKey]bool)
	visited[VisitKey{
		r:      startR,
		c:      startC,
		energy: energy,
		mask:   0,
	}] = true

	dirs := [][2]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	for queue.Len() > 0 {
		front := queue.Front()
		queue.Remove(front)

		cur := front.Value.(State)

		if cur.mask == targetMask {
			return cur.dist
		}

		if cur.energy == 0 {
			continue
		}

		for _, d := range dirs {
			nr := cur.r + d[0]
			nc := cur.c + d[1]

			if nr < 0 || nr >= m || nc < 0 || nc >= n {
				continue
			}

			cell := classroom[nr][nc]

			if cell == 'X' {
				continue
			}

			nextEnergy := cur.energy - 1

			if cell == 'R' {
				nextEnergy = energy
			}

			nextMask := cur.mask

			if cell == 'L' {
				nextMask |= 1 << litterIndex[Pos{nr, nc}]
			}

			key := VisitKey{
				r:      nr,
				c:      nc,
				energy: nextEnergy,
				mask:   nextMask,
			}

			if visited[key] {
				continue
			}

			visited[key] = true

			queue.PushBack(State{
				r:      nr,
				c:      nc,
				energy: nextEnergy,
				mask:   nextMask,
				dist:   cur.dist + 1,
			})
		}
	}

	return -1
}

The Go implementation follows the same state-space BFS strategy. Since Go does not have Python's tuple hashing, a dedicated VisitKey struct is used as the map key for visited states. The BFS queue is implemented with container/list, and all state transitions mirror the Python version exactly.

Worked Examples

Example 1

Input

classroom = ["S.",
             "XL"]

energy = 2

Litter index assignment:

Cell	Index
(1,1)	0

Target mask:

Initial state:

Position	Energy	Mask	Moves
(0,0)	2	0	0

Process BFS:

Position	Energy	Mask	Moves
(0,0)	2	0	0
(0,1)	1	0	1
(1,1)	0	1	2

Mask equals target mask.

Answer:

Example 2

Input

classroom = ["LS",
             "RL"]

energy = 4

Litter indices:

Cell	Index
(0,0)	0
(1,1)	1

Target mask:

11₂ = 3

Execution:

Position	Energy	Mask	Moves
(0,1)	4	00	0
(0,0)	3	01	1
(1,0)	4	01	2
(1,1)	3	11	3

All litter collected.

Answer:

Example 3

Input

classroom = ["L.S",
             "RXL"]

energy = 3

The obstacle blocks movement between the left and right portions of the classroom.

BFS explores every reachable state but can never obtain a mask containing both litter bits.

Answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n × energy × 2^L)	Each reachable state is processed once
Space	O(m × n × energy × 2^L)	Visited set and BFS queue store reachable states

Here:

m × n ≤ 400
energy ≤ 50
L ≤ 10

The maximum theoretical state count is:

400 × 50 × 1024 ≈ 20 million

In practice, the number of reachable states is usually much smaller because obstacles, energy restrictions, and limited litter locations greatly reduce the explored search space.

Test Cases

sol = Solution()

assert sol.minMoves(["S.", "XL"], 2) == 2  # example 1

assert sol.minMoves(["LS", "RL"], 4) == 3  # example 2

assert sol.minMoves(["L.S", "RXL"], 3) == -1  # example 3

assert sol.minMoves(["S"], 5) == 0  # no litter

assert sol.minMoves(["SL"], 1) == 1  # adjacent litter

assert sol.minMoves(["SX", "XL"], 5) == -1  # litter blocked by obstacle

assert sol.minMoves(["SRL"], 1) == 2  # reset required immediately

assert sol.minMoves(["S..L"], 3) == 3  # exact energy usage

assert sol.minMoves(["S..L"], 2) == -1  # insufficient energy

assert sol.minMoves(
    [
        "S.R",
        "...",
        "L.L",
    ],
    4,
) == 4  # multiple litter cells

assert sol.minMoves(
    [
        "S...",
        ".XX.",
        "L..L",
        "...R",
    ],
    6,
) >= 0  # larger traversable layout

assert sol.minMoves(
    [
        "SXL",
        "XXX",
        "L.R",
    ],
    10,
) == -1  # disconnected components

Test	Why
Example 1	Basic shortest path
Example 2	Multiple litter cells and reset usage
Example 3	Impossible collection scenario
`["S"]`	No litter present
`["SL"]`	Smallest nontrivial success case
Obstacle-blocked layout	Unreachable litter
`["SRL"]` with energy 1	Reset station required
Exact energy path	Uses all available energy
Insufficient energy	Cannot reach target
Multiple litter cells	Verifies bitmask handling
Larger grid	General correctness
Disconnected regions	Impossible due to topology

Edge Cases

No Litter Exists

A classroom may contain only the starting position and no litter cells at all. In this case the student has already completed the objective before making any move. The implementation detects this immediately after counting litter cells and returns 0.

Energy Reaches Zero

A common bug is incorrectly allowing movement after energy becomes zero. The rules state that movement costs one energy and cannot continue once energy is exhausted, unless the student reaches a reset cell. The implementation handles this by refusing to expand states whose remaining energy is zero.

Revisiting Cells After Collecting Litter

The shortest valid route may require returning through previously visited locations. A visited structure based only on position would incorrectly prune such paths. The implementation includes position, remaining energy, and collected-litter mask in the state, ensuring that revisiting a cell with a different collection status or energy level remains possible when necessary.

Multiple Paths to the Same Cell

Two routes may reach the same grid cell but with different energy levels or different litter masks. These are fundamentally different states because they allow different future actions. The visited set stores the complete state tuple, preventing incorrect merging of states that are not actually equivalent.

Reset Cells Used Multiple Times

A reset cell may be visited repeatedly throughout the search. The implementation does not special-case reset usage counts. Whenever the BFS enters an 'R' cell, the energy is restored to maximum, allowing unlimited reuse exactly as required by the problem statement.