<p>Given a <code>m&nbsp;* n</code>&nbsp;matrix <code>seats</code>&nbsp;&nbsp;that represent seats distributions&nbsp;in a classroom.&nbsp;If a seat&nbsp;is&nbsp;broken, it is denoted by <code>&#39;#&#39;</code> character otherwise it is denoted by a <code>&#39;.&#39;</code> character.</p>

<p>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&nbsp;directly in front or behind him. Return the <strong>maximum </strong>number of students that can take the exam together&nbsp;without any cheating being possible.</p>

<p>Students must be placed in seats in good condition.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img height="200" src="https://assets.leetcode.com/uploads/2020/01/29/image.png" width="339" />
<pre>
<strong>Input:</strong> seats = [[&quot;#&quot;,&quot;.&quot;,&quot;#&quot;,&quot;#&quot;,&quot;.&quot;,&quot;#&quot;],
&nbsp;               [&quot;.&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;.&quot;],
&nbsp;               [&quot;#&quot;,&quot;.&quot;,&quot;#&quot;,&quot;#&quot;,&quot;.&quot;,&quot;#&quot;]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> Teacher can place 4 students in available seats so they don&#39;t cheat on the exam. 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> seats = [[&quot;.&quot;,&quot;#&quot;],
&nbsp;               [&quot;#&quot;,&quot;#&quot;],
&nbsp;               [&quot;#&quot;,&quot;.&quot;],
&nbsp;               [&quot;#&quot;,&quot;#&quot;],
&nbsp;               [&quot;.&quot;,&quot;#&quot;]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> Place all students in available seats. 

</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> seats = [[&quot;#&quot;,&quot;.&quot;,&quot;<strong>.</strong>&quot;,&quot;.&quot;,&quot;#&quot;],
&nbsp;               [&quot;<strong>.</strong>&quot;,&quot;#&quot;,&quot;<strong>.</strong>&quot;,&quot;#&quot;,&quot;<strong>.</strong>&quot;],
&nbsp;               [&quot;<strong>.</strong>&quot;,&quot;.&quot;,&quot;#&quot;,&quot;.&quot;,&quot;<strong>.</strong>&quot;],
&nbsp;               [&quot;<strong>.</strong>&quot;,&quot;#&quot;,&quot;<strong>.</strong>&quot;,&quot;#&quot;,&quot;<strong>.</strong>&quot;],
&nbsp;               [&quot;#&quot;,&quot;.&quot;,&quot;<strong>.</strong>&quot;,&quot;.&quot;,&quot;#&quot;]]
<strong>Output:</strong> 10
<strong>Explanation:</strong> Place students in available seats in column 1, 3 and 5.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>seats</code>&nbsp;contains only characters&nbsp;<code>&#39;.&#39;<font face="sans-serif, Arial, Verdana, Trebuchet MS">&nbsp;and</font></code><code>&#39;#&#39;.</code></li>
	<li><code>m ==&nbsp;seats.length</code></li>
	<li><code>n ==&nbsp;seats[i].length</code></li>
	<li><code>1 &lt;= m &lt;= 8</code></li>
	<li><code>1 &lt;= n &lt;= 8</code></li>
</ul>

# bitmask dp
# https://leetcode.com/problems/maximum-students-taking-exam/solutions/504547/python3-bitmask-dp/
# https://leetcode.com/discuss/general-discussion/1125779/Dynamic-programming-on-subsets-with-examples-explained
# dp[i][mask]: maximum students in seats[:i+1] with valid mask in seats[i]
# dp[i][mask] = max(dp[i-1][mask'] + valid bit(mask))
# no adjacent students: x&(x>>1) == 0
# student on good seat: x&y == x                            (y = bit(seats[i]))
# can't see front guys: x&(y>>1) == 0 and (x>>1)&y == 0     (y = pre_mask)

class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        m, n = len(seats), len(seats[0])
        dp = [collections.defaultdict(int) for _ in range(m+1)]
        dp[-1][0] = 0
        
        bits = []
        for row in seats:
            num = 0
            for i in range(n):
                num += (row[i]=='.')<<n-1-i
            bits.append(num)
        # print(bits)
        
        for i in range(m):
            for x in range(2**n):
                for y in dp[i-1]:
                    if x&(x>>1) == 0 and x&bits[i] == x and x&(y>>1) == 0 and (x>>1)&y == 0:
                        dp[i][x] = max(dp[i][x], dp[i-1][y] + bin(x).count('1'))
        
        return max(dp[m-1][x] for x in dp[m-1])

def maxStudents(seats):
    m, n = len(seats), len(seats[0])
    
    # Function to convert a row of seats into a bitmask representing valid places
    def seat_mask(row):
        mask = 0
        for i in range(n):
            if seats[row][i] == '.':
                mask |= (1 << i)
        return mask

    # Generate all possible valid configurations of students for a row
    def valid_configs(mask):
        configs = []
        for config in range(1 << n):
            if config & mask == config and config & (config >> 1) == 0:
                configs.append(config)
        return configs
    
    dp = [{} for _ in range(m)]
    row_masks = [seat_mask(i) for i in range(m)]
    
    # Initialize the first row
    for config in valid_configs(row_masks[0]):
        dp[0][config] = bin(config).count('1')
    
    # DP over each row
    for i in range(1, m):
        for prev_config in dp[i-1]:
            for config in valid_configs(row_masks[i]):
                # Check if no cheating is possible between rows
                if (prev_config << 1) & config == 0 and (prev_config >> 1) & config == 0:
                    dp[i][config] = max(dp[i].get(config, 0), dp[i-1][prev_config] + bin(config).count('1'))
    
    # Return the maximum number of students
    return max(dp[-1].values())

16700