3568. Minimum Moves to Clean the Classroom

Description

You are given an m x n grid classroom where a student volunteer is tasked with cleaning up litter scattered around the room. Each cell in the grid is one of the following:

• 'S': Starting position of the student
• 'L': Litter that must be collected (once collected, the cell becomes empty)
• 'R': Reset area that restores the student's energy to full capacity, regardless of their current energy level (can be used multiple times)
• 'X': Obstacle the student cannot pass through
• '.': Empty space

You are also given an integer energy, representing the student's maximum energy capacity. The student starts with this energy from the starting position 'S'.

Each move to an adjacent cell (up, down, left, or right) costs 1 unit of energy. If the energy reaches 0, the student can only continue if they are on a reset area 'R', which resets the energy to its maximum capacity energy.

Return the minimum number of moves required to collect all litter items, or -1 if it's impossible.

 

Example 1:

Input: classroom = ["S.", "XL"], energy = 2

Output: 2

Explanation:

• The student starts at cell (0, 0) with 2 units of energy.
• Since cell (1, 0) contains an obstacle 'X', the student cannot move directly downward.
• A valid sequence of moves to collect all litter is as follows:
  • Move 1: From (0, 0) → (0, 1) with 1 unit of energy and 1 unit remaining.
  • Move 2: From (0, 1) → (1, 1) to collect the litter 'L'.
• The student collects all the litter using 2 moves. Thus, the output is 2.

Example 2:

Input: classroom = ["LS", "RL"], energy = 4

Output: 3

Explanation:

• The student starts at cell (0, 1) with 4 units of energy.
• A valid sequence of moves to collect all litter is as follows:
  • Move 1: From (0, 1) → (0, 0) to collect the first litter 'L' with 1 unit of energy used and 3 units remaining.
  • Move 2: From (0, 0) → (1, 0) to 'R' to reset and restore energy back to 4.
  • Move 3: From (1, 0) → (1, 1) to collect the second litter 'L'.
• The student collects all the litter using 3 moves. Thus, the output is 3.

Example 3:

Input: classroom = ["L.S", "RXL"], energy = 3

Output: -1

Explanation:

No valid path collects all 'L'.

 

Constraints:

• 1 <= m == classroom.length <= 20
• 1 <= n == classroom[i].length <= 20
• classroom[i][j] is one of 'S', 'L', 'R', 'X', or '.'
• 1 <= energy <= 50
• There is exactly one 'S' in the grid.
• There are at most 10 'L' cells in the grid.

Solutions

Solution 1: BFS

We can use Breadth-First Search (BFS) to solve this problem. First, we need to find the student's starting position and record the locations of all garbage. Then, we can use BFS to explore all possible paths starting from the initial position, while tracking the current energy and the collected garbage.

In BFS, we need to maintain a state that includes the current position, remaining energy, and a bitmask representing the collected garbage. We can use a queue to store these states and a set to record visited states to avoid revisiting them.

We start from the initial position and try to move in four directions. If we move to a garbage cell, we update the collected garbage bitmask. If we move to a reset area, we restore the energy to its maximum value. Each move consumes 1 unit of energy.

If we find a state in BFS where the garbage bitmask is 0 (meaning all garbage has been collected), we return the current number of moves. If BFS completes without finding such a state, we return -1.

The time complexity is \(O(m \times n \times \textit{energy} \times 2^{\textit{count}})\), and the space complexity is \(O(m \times n \times \textit{energy} \times 2^{\textit{count}})\), where \(m\) and \(n\) are the number of rows and columns in the grid, and \(\textit{count}\) is the number of garbage cells.

Python3JavaC++Go

class Solution:
    def minMoves(self, classroom: List[str], energy: int) -> int:
        m, n = len(classroom), len(classroom[0])
        d = [[0] * n for _ in range(m)]
        x = y = cnt = 0
        for i, row in enumerate(classroom):
            for j, c in enumerate(row):
                if c == "S":
                    x, y = i, j
                elif c == "L":
                    d[i][j] = cnt
                    cnt += 1
        if cnt == 0:
            return 0
        vis = [
            [[[False] * (1 << cnt) for _ in range(energy + 1)] for _ in range(n)]
            for _ in range(m)
        ]
        q = [(x, y, energy, (1 << cnt) - 1)]
        vis[x][y][energy][(1 << cnt) - 1] = True
        dirs = (-1, 0, 1, 0, -1)
        ans = 0
        while q:
            t = q
            q = []
            for i, j, cur_energy, mask in t:
                if mask == 0:
                    return ans
                if cur_energy <= 0:
                    continue
                for k in range(4):
                    x, y = i + dirs[k], j + dirs[k + 1]
                    if 0 <= x < m and 0 <= y < n and classroom[x][y] != "X":
                        nxt_energy = (
                            energy if classroom[x][y] == "R" else cur_energy - 1
                        )
                        nxt_mask = mask
                        if classroom[x][y] == "L":
                            nxt_mask &= ~(1 << d[x][y])
                        if not vis[x][y][nxt_energy][nxt_mask]:
                            vis[x][y][nxt_energy][nxt_mask] = True
                            q.append((x, y, nxt_energy, nxt_mask))
            ans += 1
        return -1

class Solution {
    public int minMoves(String[] classroom, int energy) {
        int m = classroom.length, n = classroom[0].length();
        int[][] d = new int[m][n];
        int x = 0, y = 0, cnt = 0;
        for (int i = 0; i < m; i++) {
            String row = classroom[i];
            for (int j = 0; j < n; j++) {
                char c = row.charAt(j);
                if (c == 'S') {
                    x = i;
                    y = j;
                } else if (c == 'L') {
                    d[i][j] = cnt;
                    cnt++;
                }
            }
        }
        if (cnt == 0) {
            return 0;
        }
        boolean[][][][] vis = new boolean[m][n][energy + 1][1 << cnt];
        List<int[]> q = new ArrayList<>();
        q.add(new int[] {x, y, energy, (1 << cnt) - 1});
        vis[x][y][energy][(1 << cnt) - 1] = true;
        int[] dirs = {-1, 0, 1, 0, -1};
        int ans = 0;
        while (!q.isEmpty()) {
            List<int[]> t = q;
            q = new ArrayList<>();
            for (int[] state : t) {
                int i = state[0], j = state[1], curEnergy = state[2], mask = state[3];
                if (mask == 0) {
                    return ans;
                }
                if (curEnergy <= 0) {
                    continue;
                }
                for (int k = 0; k < 4; k++) {
                    int nx = i + dirs[k], ny = j + dirs[k + 1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && classroom[nx].charAt(ny) != 'X') {
                        int nxtEnergy = classroom[nx].charAt(ny) == 'R' ? energy : curEnergy - 1;
                        int nxtMask = mask;
                        if (classroom[nx].charAt(ny) == 'L') {
                            nxtMask &= ~(1 << d[nx][ny]);
                        }
                        if (!vis[nx][ny][nxtEnergy][nxtMask]) {
                            vis[nx][ny][nxtEnergy][nxtMask] = true;
                            q.add(new int[] {nx, ny, nxtEnergy, nxtMask});
                        }
                    }
                }
            }
            ans++;
        }
        return -1;
    }
}

class Solution {
public:
    int minMoves(vector<string>& classroom, int energy) {
        int m = classroom.size(), n = classroom[0].size();
        vector<vector<int>> d(m, vector<int>(n, 0));
        int x = 0, y = 0, cnt = 0;
        for (int i = 0; i < m; ++i) {
            string& row = classroom[i];
            for (int j = 0; j < n; ++j) {
                char c = row[j];
                if (c == 'S') {
                    x = i;
                    y = j;
                } else if (c == 'L') {
                    d[i][j] = cnt;
                    cnt++;
                }
            }
        }
        if (cnt == 0) {
            return 0;
        }
        vector<vector<vector<vector<bool>>>> vis(m, vector<vector<vector<bool>>>(n, vector<vector<bool>>(energy + 1, vector<bool>(1 << cnt, false))));
        queue<tuple<int, int, int, int>> q;
        q.emplace(x, y, energy, (1 << cnt) - 1);
        vis[x][y][energy][(1 << cnt) - 1] = true;
        vector<int> dirs = {-1, 0, 1, 0, -1};
        int ans = 0;
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                auto [i, j, cur_energy, mask] = q.front();
                q.pop();
                if (mask == 0) {
                    return ans;
                }
                if (cur_energy <= 0) {
                    continue;
                }
                for (int k = 0; k < 4; ++k) {
                    int nx = i + dirs[k], ny = j + dirs[k + 1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && classroom[nx][ny] != 'X') {
                        int nxt_energy = classroom[nx][ny] == 'R' ? energy : cur_energy - 1;
                        int nxt_mask = mask;
                        if (classroom[nx][ny] == 'L') {
                            nxt_mask &= ~(1 << d[nx][ny]);
                        }
                        if (!vis[nx][ny][nxt_energy][nxt_mask]) {
                            vis[nx][ny][nxt_energy][nxt_mask] = true;
                            q.emplace(nx, ny, nxt_energy, nxt_mask);
                        }
                    }
                }
            }
            ans++;
        }
        return -1;
    }
};

func minMoves(classroom []string, energy int) int {
    m, n := len(classroom), len(classroom[0])
    d := make([][]int, m)
    for i := range d {
        d[i] = make([]int, n)
    }
    x, y, cnt := 0, 0, 0
    for i := 0; i < m; i++ {
        row := classroom[i]
        for j := 0; j < n; j++ {
            c := row[j]
            if c == 'S' {
                x, y = i, j
            } else if c == 'L' {
                d[i][j] = cnt
                cnt++
            }
        }
    }
    if cnt == 0 {
        return 0
    }

    vis := make([][][][]bool, m)
    for i := range vis {
        vis[i] = make([][][]bool, n)
        for j := range vis[i] {
            vis[i][j] = make([][]bool, energy+1)
            for e := range vis[i][j] {
                vis[i][j][e] = make([]bool, 1<<cnt)
            }
        }
    }
    type state struct {
        i, j, curEnergy, mask int
    }
    q := []state{{x, y, energy, (1 << cnt) - 1}}
    vis[x][y][energy][(1<<cnt)-1] = true
    dirs := []int{-1, 0, 1, 0, -1}
    ans := 0

    for len(q) > 0 {
        t := q
        q = []state{}
        for _, s := range t {
            i, j, curEnergy, mask := s.i, s.j, s.curEnergy, s.mask
            if mask == 0 {
                return ans
            }
            if curEnergy <= 0 {
                continue
            }
            for k := 0; k < 4; k++ {
                nx, ny := i+dirs[k], j+dirs[k+1]
                if nx >= 0 && nx < m && ny >= 0 && ny < n && classroom[nx][ny] != 'X' {
                    var nxtEnergy int
                    if classroom[nx][ny] == 'R' {
                        nxtEnergy = energy
                    } else {
                        nxtEnergy = curEnergy - 1
                    }
                    nxtMask := mask
                    if classroom[nx][ny] == 'L' {
                        nxtMask &= ^(1 << d[nx][ny])
                    }
                    if !vis[nx][ny][nxtEnergy][nxtMask] {
                        vis[nx][ny][nxtEnergy][nxtMask] = true
                        q = append(q, state{nx, ny, nxtEnergy, nxtMask})
                    }
                }
            }
        }
        ans++
    }
    return -1
}

Comments