Given a m * n matrix seats that represent seats distributions in a classroom. If a seat is broken, it is denoted by '#' character otherwise it is denoted by a '.' character.
Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot see the answers of the student sitting directly in front or behind him. Return the maximum number of students that can take the exam together without any cheating being possible.
Students must be placed in seats in good condition.
Input: seats =[["#",".","#","#",".","#"],[".","#","#","#","#","."],["#",".","#","#",".","#"]]Output: 4Explanation: Teacher can place 4 students in available seats so they don't cheat on the exam.
Input: seats =[["#",".",".",".","#"],[".","#",".","#","."],[".",".","#",".","."],[".","#",".","#","."],["#",".",".",".","#"]]Output: 10Explanation: Place students in available seats in column 1,3 and 5.
We use bitmask dynamic programming to represent all possible valid seatings for each row. For each row, we try all possible seatings that do not violate the cheating constraints and are compatible with the previous row’s seating. The bitmask allows us to efficiently check for conflicts and maximize the number of students.
For each row, generate all possible seatings using bitmask, only placing students in good seats (’.’).
For each seating, ensure no two students are adjacent (left/right) in the same row.
Use DP to keep track of the maximum students for each valid seating in the current row, considering compatibility with the previous row (no cheating via upper left/right).
Iterate through all rows, updating the DP table for each possible seating.
The answer is the maximum value in the last row’s DP table.
classSolution {
funmaxStudents(seats: Array<CharArray>): Int {
val m = seats.size
val n = seats[0].size
val dp = Array(m) { IntArray(1 shl n) { -1 } }
for (mask in0 until (1 shl n)) {
var ok = truefor (j in0 until n) {
if ((mask shr j) and 1==1&& seats[0][j] =='#') ok = falseif ((mask shr j) and 1==1&& j > 0&& (mask shr (j-1)) and 1==1) ok = false }
if (ok) dp[0][mask] = mask.countOneBits()
}
for (i in1 until m) {
for (mask in0 until (1 shl n)) {
var ok = truefor (j in0 until n) {
if ((mask shr j) and 1==1&& seats[i][j] =='#') ok = falseif ((mask shr j) and 1==1&& j > 0&& (mask shr (j-1)) and 1==1) ok = false }
if (!ok) continuefor (pmask in0 until (1 shl n)) {
if (dp[i-1][pmask] == -1) continuevar compatible = truefor (j in0 until n) {
if ((mask shr j) and 1==1&& ((j > 0&& (pmask shr (j-1)) and 1==1) || (j < n-1&& (pmask shr (j+1)) and 1==1))) compatible = false }
if (compatible) dp[i][mask] = maxOf(dp[i][mask], dp[i-1][pmask] + mask.countOneBits())
}
}
}
var ans = 0for (mask in0 until (1 shl n)) ans = maxOf(ans, dp[m-1][mask])
return ans
}
}
⏰ Time complexity: O(m * n * 2^n * 2^n), where m is the number of rows and n is the number of columns. For each row, we check all possible seatings and all previous seatings.