3568.minimum-moves-to-clean-the-classroom.md

3568. Minimum Moves to Clean the Classroom

Multi-state BFS

data class State(
    val x: Int, 
    val y: Int, 
    val energy: Int,
    val mask: Int,
    val moves: Int
)

fun minMoves(classroom: Array<String>, E: Int): Int {
    val m = classroom.size
    val n = classroom[0].length

    // search starting point + all positions of litter
    // state: (x, y), remaining energy, collected litter 
    val allLitter = mutableListOf<Pair<Int, Int>>()
    var start = 0 to 0
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (classroom[i][j] == 'S') {
                start = i to j
            } else if (classroom[i][j] == 'L') {
                allLitter.add(i to j)
            }
        }
    }
    val l = allLitter.size
    val indexMap = Array(m) { IntArray(n) { -1 } }
    for (i in 0 until l) {
        val (x, y) = allLitter[i]
        indexMap[x][y] = i
    }
    val queue = ArrayDeque<State>()
    val visited = Array(m) {
        Array(n) {
            Array(E + 1) {
                BooleanArray(1 shl l)
            }
        }
    }
    val initMask = 0
    val startSet = HashSet<Pair<Int, Int>>()
    queue.addLast(State(
        start.first, start.second,
        E,
        initMask,
        0
    ))
    visited[start.first][start.second][E][initMask] = true
    while (queue.isNotEmpty()) {
        val current = queue.removeFirst()
        if (current.mask == (1 shl l) - 1) {
            return current.moves
        }

        var ee = current.energy
        val x = current.x
        val y = current.y
        if (classroom[x][y] == 'R') {
            ee = E
        }
        for (d in directions) {
            val newX = x + d[0]
            val newY = y + d[1]
            if (newX !in 0 until m || newY !in 0 until n) continue
            if (classroom[newX][newY] == 'X') continue
            if (ee <= 0) continue

            val nextEE = ee - 1

            var nextMask = current.mask
            val id = indexMap[newX][newY]
            if (id != -1) {
                nextMask = nextMask or (1 shl id)
            }
            
            if (visited[newX][newY][nextEE][nextMask].not()) {
                queue.addLast(State(
                    newX, newY,
                    nextEE,
                    nextMask,
                    current.moves + 1
                ))
                visited[newX][newY][nextEE][nextMask] = true
            }
        }
    }
    return -1
}