<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>

class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        m, n = len(seats), len(seats[0])
        dp = [[-1 for _ in range((1<<n)+1)] for _ in range(m)]
        for j in range((1<<n)+1):
            if not self.valid(seats[-1], j): continue
            dp[-1][j] = self.countSeated(seats[-1], j)

        answer = max(dp[-1])
        for i in range(m-2, -1, -1):
            for curr in range((1<<n)+1):
                if not self.valid(seats[i], curr): continue

                for pre in range((1<<n)+1):
                    if dp[i+1][pre] == -1: continue
                    banned = self.updateRow(seats[i], pre)
                    if not self.valid(seats[i], curr):
                        self.recoverRow(seats[i], banned)
                        continue
                    
                    dp[i][curr] = max(dp[i][curr], dp[i+1][pre] + self.countSeated(seats[i], curr))
                    self.recoverRow(seats[i], banned)

                answer = max(answer, dp[i][curr])
        return answer

    def valid(self, row, mask):
        n = len(row)
        seated = []
        for j in range(n):
            if ((1 << j) & mask) and row[j] == '#': return False
            if ((1 << j) & mask):
                seated.append(j)

        for j in range(len(seated)-1):
            if seated[j+1] - seated[j] == 1: return False
        return True

    def countSeated(self, row, mask):
        n = len(row)
        count = 0
        for j in range(n):
            if ((1<<j) & mask) and row[j] == '.':
                count += 1
        return count


    def updateRow(self, row, pre):
        n = len(row)
        banned = set()
        for j in range(n):
            if not (1 << j) & pre: continue
            if j-1 >= 0 and row[j-1] == '.':
                row[j-1] = '#'
                banned.add(j-1)
            if j+1 < n and row[j+1] == '.':
                row[j+1] = '#'
                banned.add(j+1)
        return banned

    def recoverRow(self, row, banned):
        for j in banned:
            row[j] = '.'
        

140