3568. Minimum Moves to Clean the Classroom

Array Matrix Breadth-First Search Bit Manipulation

Problem Overview

You start at S with a fixed energy budget per stretch between recharge tiles R.

Intuition

You start at S with a fixed energy budget per stretch between recharge tiles R. Each move costs one energy unless you step onto R, which refills you. Every litter cell L must be visited at least once. The fewest moves is a shortest path in state space: position, remaining energy, and which litter spots are still dirty. Breadth-first search on that graph finds the answer.

Algorithm

1Map each L cell to one bit in a mask. Start with all bits set at S with full energy.
2BFS queue states (row, col, energy, mask). Mark visited in a 4D table.
3From each state, try the four neighbors that are not walls X.
4On R, reset energy to the maximum. On L, clear that bit. Other tiles cost one energy.
5The first dequeued state with mask 0 is reached at minimum depth. Return -1 if the queue empties.

Example Walkthrough

Input: classroom with S, one L, one R, energy = 3

1.Walk from S toward L, spending energy each step.
2.If energy runs low, route through R to refill before reaching every L.
3.When the litter mask becomes 0, return the BFS layer count.

Output: minimum move count

Common Pitfalls

•Energy must stay in the visited state. Same cell and mask with more energy can still matter.
•Stepping onto R sets energy to the full budget, not plus one.
•If there is no litter, return 0 without running BFS.
•Precompute a bit per litter cell so clearing uses mask & ~bit instead of recomputing indices.

3568.cs

// Approach: BFS on (row, col, energy, litter bitmask). Start at S with full
// energy and all litter bits set; stepping on L clears that bit, R refills
// energy. First time mask is 0 gives the minimum move count.
// Complexity: O(m * n * energy * 2^L) time and space (L = litter cells).
public class Solution
{
    public int MinMoves(string[] classroom, int energy)
    {
        int m = classroom.Length;
        int n = classroom[0].Length;
        char[][] grid = new char[m][];
        int[,] litBit = new int[m, n];
        int sx = 0, sy = 0, lit = 0;

        for (int i = 0; i < m; i++)
        {
            grid[i] = classroom[i].ToCharArray();
            for (int j = 0; j < n; j++)
            {
                char c = grid[i][j];
                if (c == 'S')
                {
                    sx = i;
                    sy = j;
                }
                else if (c == 'L')
                    litBit[i, j] = 1 << lit++;
            }
        }

        if (lit == 0)
            return 0;

        int maskSize = 1 << lit;
        bool[,,,] vis = new bool[m, n, energy + 1, maskSize];
        var q = new Queue<(int x, int y, int e, int mask)>();
        int startMask = maskSize - 1;

        vis[sx, sy, energy, startMask] = true;
        q.Enqueue((sx, sy, energy, startMask));

        int[] dx = { -1, 0, 1, 0 };
        int[] dy = { 0, 1, 0, -1 };
        int steps = 0;

        while (q.Count > 0)
        {
            int size = q.Count;
            while (size-- > 0)
            {
                var (x, y, e, mask) = q.Dequeue();
                if (mask == 0)
                    return steps;
                if (e == 0)
                    continue;

                for (int d = 0; d < 4; d++)
                {
                    int nx = x + dx[d];
                    int ny = y + dy[d];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n)
                        continue;

                    char cell = grid[nx][ny];
                    if (cell == 'X')
                        continue;

                    int ne = cell == 'R' ? energy : e - 1;
                    int nmask = mask & ~litBit[nx, ny];

                    if (vis[nx, ny, ne, nmask])
                        continue;

                    vis[nx, ny, ne, nmask] = true;
                    q.Enqueue((nx, ny, ne, nmask));
                }
            }
            steps++;
        }

        return -1;
    }
}

Was this solution helpful?