3568. Minimum Moves to Clean the Classroom

import java.util.*;

class Solution {
    public int minMoves(String[] classroom, int energy) {
        int m = classroom.length;
        int n = classroom[0].length();

        int startR = -1, startC = -1;
        List<int[]> litters = new ArrayList<>();
        boolean[][] isReset = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = classroom[i].charAt(j);
                if (c == 'S') { startR = i; startC = j; }
                else if (c == 'L') litters.add(new int[]{i, j});
                else if (c == 'R') isReset[i][j] = true;
            }
        }

        int totalLitter = litters.size();
        int fullMask = (1 << totalLitter) - 1;

        // Map litter position -> index
        Map<Integer, Integer> litterIndex = new HashMap<>();
        for (int k = 0; k < totalLitter; k++) {
            litterIndex.put(litters.get(k)[0] * n + litters.get(k)[1], k);
        }

        boolean[][][][] visited = new boolean[m][n][energy + 1][fullMask + 1];

        Queue<int[]> queue = new LinkedList<>();

        int initMask = 0;

        Integer startLitter = litterIndex.get(startR * n + startC);
        if (startLitter != null) initMask |= (1 << startLitter);

        queue.offer(new int[]{startR, startC, energy, initMask, 0});
        visited[startR][startC][energy][initMask] = true;

        int[] dirs = {-1, 0, 1, 0, 0, -1, 0, 1};

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1], e = cur[2], mask = cur[3], moves = cur[4];

            if (mask == fullMask) return moves;

            if (e == 0) continue;

            for (int d = 0; d < 4; d++) {
                int nr = r + dirs[d * 2];
                int nc = c + dirs[d * 2 + 1];

                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                if (classroom[nr].charAt(nc) == 'X') continue;

                int ne = e - 1;
                // If landed on reset area, restore energy
                if (isReset[nr][nc]) ne = energy;

                // Collect litter if present
                int newMask = mask;
                Integer li = litterIndex.get(nr * n + nc);
                if (li != null) newMask |= (1 << li);

                if (!visited[nr][nc][ne][newMask]) {
                    visited[nr][nc][ne][newMask] = true;
                    queue.offer(new int[]{nr, nc, ne, newMask, moves + 1});
                }
            }
        }

        return -1; // impossible
    }
}

from collections import deque

class Solution:
    def minMoves(self, classroom, energy):
        m = len(classroom)
        n = len(classroom[0])

        startR = startC = -1
        litters = []
        isReset = [[False] * n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                c = classroom[i][j]

                if c == 'S':
                    startR, startC = i, j
                elif c == 'L':
                    litters.append((i, j))
                elif c == 'R':
                    isReset[i][j] = True

        totalLitter = len(litters)
        fullMask = (1 << totalLitter) - 1

        litterIndex = {}
        for k, (r, c) in enumerate(litters):
            litterIndex[r * n + c] = k

        visited = set()
        queue = deque()

        initMask = 0
        if startR * n + startC in litterIndex:
            initMask |= 1 << litterIndex[startR * n + startC]

        queue.append((startR, startC, energy, initMask, 0))
        visited.add((startR, startC, energy, initMask))

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

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

            if mask == fullMask:
                return moves

            if e == 0:
                continue

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

                if nr < 0 or nr >= m or nc < 0 or nc >= n:
                    continue

                if classroom[nr][nc] == 'X':
                    continue

                ne = e - 1

                if isReset[nr][nc]:
                    ne = energy

                newMask = mask
                key = nr * n + nc

                if key in litterIndex:
                    newMask |= 1 << litterIndex[key]

                state = (nr, nc, ne, newMask)

                if state not in visited:
                    visited.add(state)
                    queue.append((nr, nc, ne, newMask, moves + 1))

        return -1

class Solution {
public:
    int minMoves(vector<string>& classroom, int energy) {
        int m = classroom.size();
        int n = classroom[0].size();

        int startR = -1, startC = -1;
        vector<pair<int, int>> litters;
        vector<vector<bool>> isReset(m, vector<bool>(n, false));

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = classroom[i][j];

                if (c == 'S') {
                    startR = i;
                    startC = j;
                } else if (c == 'L') {
                    litters.push_back({i, j});
                } else if (c == 'R') {
                    isReset[i][j] = true;
                }
            }
        }

        int totalLitter = litters.size();
        int fullMask = (1 << totalLitter) - 1;

        map<int, int> litterIndex;

        for (int i = 0; i < totalLitter; i++) {
            int r = litters[i].first;
            int c = litters[i].second;
            litterIndex[r * n + c] = i;
        }

        vector<vector<vector<vector<bool>>>> visited(
            m,
            vector<vector<vector<bool>>>(
                n,
                vector<vector<bool>>(
                    energy + 1,
                    vector<bool>(fullMask + 1, false)
                )
            )
        );

        queue<vector<int>> q;

        int initMask = 0;
        int startKey = startR * n + startC;

        if (litterIndex.count(startKey)) {
            initMask |= 1 << litterIndex[startKey];
        }

        q.push({startR, startC, energy, initMask, 0});
        visited[startR][startC][energy][initMask] = true;

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

        while (!q.empty()) {
            auto cur = q.front();
            q.pop();

            int r = cur[0];
            int c = cur[1];
            int e = cur[2];
            int mask = cur[3];
            int moves = cur[4];

            if (mask == fullMask)
                return moves;

            if (e == 0)
                continue;

            for (auto& dir : dirs) {
                int nr = r + dir[0];
                int nc = c + dir[1];

                if (nr < 0 || nr >= m || nc < 0 || nc >= n)
                    continue;

                if (classroom[nr][nc] == 'X')
                    continue;

                int ne = e - 1;

                if (isReset[nr][nc])
                    ne = energy;

                int newMask = mask;
                int key = nr * n + nc;

                if (litterIndex.count(key)) {
                    newMask |= 1 << litterIndex[key];
                }

                if (!visited[nr][nc][ne][newMask]) {
                    visited[nr][nc][ne][newMask] = true;
                    q.push({nr, nc, ne, newMask, moves + 1});
                }
            }
        }

        return -1;
    }
};

class Solution {
    minMoves(classroom, energy) {
        const m = classroom.length;
        const n = classroom[0].length;

        let startR = -1;
        let startC = -1;

        const litters = [];
        const isReset = Array.from(
            { length: m },
            () => Array(n).fill(false)
        );

        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                const c = classroom[i][j];

                if (c === 'S') {
                    startR = i;
                    startC = j;
                } else if (c === 'L') {
                    litters.push([i, j]);
                } else if (c === 'R') {
                    isReset[i][j] = true;
                }
            }
        }

        const totalLitter = litters.length;
        const fullMask = (1 << totalLitter) - 1;

        const litterIndex = new Map();

        for (let i = 0; i < totalLitter; i++) {
            const [r, c] = litters[i];
            litterIndex.set(r * n + c, i);
        }

        const visited = new Set();
        const queue = [];

        let initMask = 0;
        const startKey = startR * n + startC;

        if (litterIndex.has(startKey)) {
            initMask |= 1 << litterIndex.get(startKey);
        }

        queue.push([
            startR,
            startC,
            energy,
            initMask,
            0
        ]);

        visited.add(
            `${startR},${startC},${energy},${initMask}`
        );

        let front = 0;

        const dirs = [
            [-1, 0],
            [1, 0],
            [0, -1],
            [0, 1]
        ];

        while (front < queue.length) {
            const [r, c, e, mask, moves] = queue[front++];

            if (mask === fullMask) {
                return moves;
            }

            if (e === 0) {
                continue;
            }

            for (const [dr, dc] of dirs) {
                const nr = r + dr;
                const nc = c + dc;

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

                if (classroom[nr][nc] === 'X') {
                    continue;
                }

                let ne = e - 1;

                if (isReset[nr][nc]) {
                    ne = energy;
                }

                let newMask = mask;
                const key = nr * n + nc;

                if (litterIndex.has(key)) {
                    newMask |= 1 << litterIndex.get(key);
                }

                const state =
                    `${nr},${nc},${ne},${newMask}`;

                if (!visited.has(state)) {
                    visited.add(state);

                    queue.push([
                        nr,
                        nc,
                        ne,
                        newMask,
                        moves + 1
                    ]);
                }
            }
        }

        return -1;
    }
}