Hard

Minimum Moves to Clean the Classroom

LAB

Grid rows contain S start, L litter, X walls, and . open cells. Return the minimum steps to collect all litter, or -1.

EXAMPLES

Example 1

Input
{
  "grid": [
    "S.L",
    "...",
    "L.."
  ]
}

Output
6

FUNCTION SHAPE

grid: stringArray→int

SOLUTION NOTE

Since L is up to 10, we can use a bitmask. We use this as an efficient way to track which litters we have already picked up as part of our state in the BFS. Note we also need a litter map from (i,j) -> index of the litter, in order to determine which bit in our litter bitmask represents the current litter. Our state is: (i,j,e, litter_bitmask, level), ie. the current location i,j, the current energy e, the litter we have remaining, and level represents the number of moves to reach this state. We use XOR (^) to flip a 1 bit to 0, indicating we have collected this litter.

The visited set is actually a dictionary mapping (i,j,litter_bitmask) to the maximum energy required to reach this triple. We do not need level, because if we re-visit this (i,j,litter_bitmask) state with a higher level, it is redundant. Also, by removing energy <= 50 from the tuple we save a lot of time/space in visited. This is possible, because if we reach (i,j,litter_bitmask) with a lower energy, it is a greedily suboptimal state.

Reveal reference solution +

pythonREFERENCE

def minMoves(self, classroom: List[str], energy: int) -> int:
    m,n = len(classroom), len(classroom[0])
    q = deque()
    count_litter = 0
    litter_bitmask = 0
    litter_map = defaultdict(int) # (i,j) -> index of litter

    for i in range(m):
        for j in range(n):
            if classroom[i][j] == 'L':
                litter_bitmask |= 1 << count_litter
                litter_map[(i,j)] = count_litter
                count_litter += 1

    if count_litter == 0: return 0

    visited = defaultdict(lambda: -inf)

    for i in range(m):
        for j in range(n):
            if classroom[i][j] == 'S':
                visited[(i,j,litter_bitmask)] = energy
                q.append((i,j,energy, litter_bitmask))

    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
    def isInBounds(i,j):
        return 0 <= i < m and 0 <= j < n

    level = 0
    while q:
        for _ in range(len(q)):
            i,j,e,litter_bitmask= q.popleft()
            litter_remaining = litter_bitmask.bit_count()
            if litter_remaining == 0: return level

            for x,y in dirs:
                ii,jj = i+x,j+y
                if not isInBounds(ii,jj) or classroom[ii][jj] == 'X': continue
                can_collect_litter = classroom[ii][jj] == 'L' and (1 << litter_map[(ii,jj)]) & litter_bitmask > 0
                can_restore_energy = classroom[ii][jj] == 'R'
                if e-1 < 0: continue
                e_ = energy if can_restore_energy else e-1
                if visited[(ii,jj,litter_bitmask)] >= e_: continue
                visited[(ii,jj,litter_bitmask)] = e_
                q.append((ii,jj, e_, litter_bitmask ^ (1 << litter_map[(ii,jj)]) if can_collect_litter else litter_bitmask))
        level += 1

    return -1

TimeO(m*n*2^L*E)

SpaceO(m*n*2^L)

Open on LeetCode ↗