Maximum Students Taking Exam

Similar Problems:

- CheatSheet: LeetCode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #dynamicprogramming, #bitmaskdp

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: 4 Explanation: Teacher can place 4 students in available seats so they don't cheat on the exam.

Example 2:

Input: seats = [[".","#"], ["#","#"], ["#","."], ["#","#"], [".","#"]] Output: 3 Explanation: Place all students in available seats.

Example 3:

Input: seats = [["#",".",".",".","#"], [".","#",".","#","."], [".",".","#",".","."], [".","#",".","#","."], ["#",".",".",".","#"]] Output: 10 Explanation: Place students in available seats in column 1, 3 and 5.

Constraints:

- seats contains only characters ‘.’ and’#’.
- m == seats.length
- n == seats[i].length
- 1 <= m <= 8
- 1 <= n <= 8

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

## https://code.dennyzhang.com/maximum-students-taking-exam ## Basic Ideas: dynamic programming + bitmask ## ## 1. For each row, try all the possiblities ## 2. How we confirm no adjacent students in one row? ## Use bitmask for each row. 1 represent, it's taken ## Fact: For X, if X & (X<<1) == 0, there are no two adjacent 1s in its binary representation ## 3. dp[r][mask] = max(dp[r][mask], dp[r - 1][prev_mask] + bit_count(mask) ## ## Complexity: Time ?, Space ? class Solution: def maxStudents(self, seats: List[List[str]]) -> int: m, n = len(seats), len(seats[0]) dp = [collections.defaultdict(lambda: -1) for _ in range(m+1)] dp[0][0] = 0 res = 0 for i in range(1, m+1): # print(i, dp[0], dp[0][0]) rowState = 0 for j in range(n): # 0s in rowState means broken seats rowState = 2*rowState + (seats[i-1][j] == '.') for s2 in range(2**n): # make sure the state is valid if s2 & rowState != s2: continue # adjacent students in this row if s2 & (s2>>1) != 0: continue for s1 in range(2**n): # check upper left if s2 & (s1>>1) != 0: continue # check upper right if s2 & (s1<<1) != 0: continue # s1 is valid in previous row if dp[i-1][s1] != -1: dp[i][s2] = max(dp[i][s2], dp[i-1][s1]+f'{s2:b}'.count('1')) if i == m: res = max(res, dp[i][s2]) return res