LeetCode 3568 - Minimum Moves to Clean the Classroom

LeetCode Problem 3568

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

Solution

Problem Understanding

The problem asks us to compute the minimum number of moves a student must make to collect all litter 'L' in a classroom represented as an m x n grid. The student starts at 'S' with a finite energy that decreases by 1 with each step. Cells 'R' allow the student to restore energy to full, while 'X' represents impassable obstacles. Empty cells '.' do not impact energy except for the movement cost.

The input classroom is a list of strings, each representing a row. The output is an integer representing the minimum moves to collect all litter or -1 if it is impossible. The constraints indicate that the grid is small (m, n <= 20) but there can be multiple litter items (<= 10), meaning enumerating all possible litter collection sequences is feasible with proper pruning. The maximum energy is 50, so the algorithm must carefully track energy to avoid invalid paths.

Important edge cases include:

• Litter completely blocked by obstacles.
• Energy too small to reach any litter without using a reset 'R'.
• Multiple litter and reset cells that require a specific order to minimize moves.

Approaches

A brute-force approach would attempt to simulate all possible sequences of moves from 'S', updating the energy at each step, and checking every permutation of litter collection. This guarantees correctness but is infeasible, because the state space is O((mn * energy)^k) where k is the number of litter pieces, leading to exponential growth.

The key insight is that the problem can be reduced to a state-space search over (position, energy, litter_collected_bitmask). Using Breadth-First Search (BFS) ensures that the first time we reach a state where all litter is collected, the move count is minimal. We only explore states where remaining energy is non-negative, and energy is reset at 'R' cells. The small number of litter pieces (<= 10) allows representing collected litter as a bitmask, making BFS efficient and memory-manageable.

Algorithm Walkthrough

1. Preprocessing: Scan the grid to identify the starting position 'S', litter positions 'L', and reset positions 'R'. Assign each litter an index from 0 to k-1 for the bitmask.
2. Initialization: Create a queue for BFS. Each state is represented as (x, y, remaining_energy, litter_mask, moves). Initialize the queue with the starting position, full energy, no litter collected, and zero moves. Also maintain a visited set or array to avoid revisiting identical states (x, y, energy, litter_mask).
3. BFS Traversal: While the queue is not empty, pop a state (x, y, e, mask, moves) and explore all 4 adjacent cells. For each move:

• Ignore cells outside the grid or with obstacles 'X'.
• Deduct 1 energy for the move. If moving to 'R', reset energy to full.
• If moving onto a litter 'L', update the bitmask by setting the corresponding bit.
• If the new state (nx, ny, new_energy, new_mask) is not visited, add it to the queue with moves + 1.

4. Termination Condition: If at any point the litter mask equals (1 << k) - 1 (all litter collected), return the number of moves taken. If the queue empties without reaching this mask, return -1.
5. State Pruning: To ensure efficiency, skip states that have already been visited with greater or equal remaining energy for the same litter mask, since a better path exists.

Why it works: BFS guarantees that the first time we reach a complete litter collection mask, the path is minimal because BFS explores states in increasing order of move count. The bitmask ensures that the algorithm distinguishes different sequences of litter collection, and energy tracking ensures only valid movements are considered.

Python Solution

from collections import deque
from typing import List, Tuple

class Solution:
    def minMoves(self, classroom: List[str], energy: int) -> int:
        m, n = len(classroom), len(classroom[0])
        litter_positions = {}
        start = None
        for i in range(m):
            for j in range(n):
                if classroom[i][j] == 'S':
                    start = (i, j)
                elif classroom[i][j] == 'L':
                    litter_positions[(i, j)] = len(litter_positions)
        
        total_litter = len(litter_positions)
        target_mask = (1 << total_litter) - 1
        visited = [[[[-1]*(1<<total_litter) for _ in range(energy+1)] for _ in range(n)] for _ in range(m)]
        
        queue = deque()
        sx, sy = start
        visited[sx][sy][energy][0] = 0
        queue.append((sx, sy, energy, 0, 0))
        
        directions = [(-1,0),(1,0),(0,-1),(0,1)]
        
        while queue:
            x, y, e, mask, moves = queue.popleft()
            if mask == target_mask:
                return moves
            for dx, dy in directions:
                nx, ny = x+dx, y+dy
                if 0 <= nx < m and 0 <= ny < n and classroom[nx][ny] != 'X':
                    ne = e-1
                    if ne < 0:
                        continue
                    if classroom[nx][ny] == 'R':
                        ne = energy
                    nmask = mask
                    if (nx, ny) in litter_positions:
                        nmask |= (1 << litter_positions[(nx, ny)])
                    if visited[nx][ny][ne][nmask] == -1:
                        visited[nx][ny][ne][nmask] = moves+1
                        queue.append((nx, ny, ne, nmask, moves+1))
        return -1

Explanation: The preprocessing step identifies the starting position and maps each litter to a unique bitmask index. The BFS queue stores (x, y, energy, litter_mask, moves). At each step, all valid moves are explored, energy is deducted, reset if needed, and litter collection is updated in the bitmask. A 4D visited array prevents redundant exploration.

Go Solution

package main

import "container/list"

func minMoves(classroom []string, energy int) int {
    m, n := len(classroom), len(classroom[0])
    type state struct{ x, y, e, mask, moves int }
    litterPositions := make(map[[2]int]int)
    var sx, sy int
    idx := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            switch classroom[i][j] {
            case 'S':
                sx, sy = i, j
            case 'L':
                litterPositions[[2]int{i, j}] = idx
                idx++
            }
        }
    }
    totalLitter := len(litterPositions)
    targetMask := (1 << totalLitter) - 1
    visited := make([][][][]bool, m)
    for i := range visited {
        visited[i] = make([][][]bool, n)
        for j := range visited[i] {
            visited[i][j] = make([][]bool, energy+1)
            for k := range visited[i][j] {
                visited[i][j][k] = make([]bool, 1<<totalLitter)
            }
        }
    }
    q := list.New()
    visited[sx][sy][energy][0] = true
    q.PushBack(state{sx, sy, energy, 0, 0})
    directions := [][2]int{{-1,0},{1,0},{0,-1},{0,1}}
    
    for q.Len() > 0 {
        e := q.Front()
        q.Remove(e)
        curr := e.Value.(state)
        if curr.mask == targetMask {
            return curr.moves
        }
        for _, d := range directions {
            nx, ny := curr.x+d[0], curr.y+d[1]
            if nx >= 0 && nx < m && ny >= 0 && ny < n && classroom[nx][ny] != 'X' {
                ne := curr.e - 1
                if ne < 0 {
                    continue
                }
                if classroom[nx][ny] == 'R' {
                    ne = energy
                }
                nmask := curr.mask
                if idx, ok := litterPositions[[2]int{nx, ny}]; ok {
                    nmask |= 1 << idx
                }
                if !visited[nx][ny][ne][nmask] {
                    visited[nx][ny][ne][nmask] = true
                    q.PushBack(state{nx, ny