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

# from functools import cache
# from typing import List

# class Solution:
#     def maxStudents(self, seats: List[List[str]]) -> int:
#         m, n = len(seats), len(seats[0])

#         def check(col: int, p: str) -> bool:
#             if col > 0 and p[col - 1] == '1':
#                 return False
#             if col < n - 1 and p[col + 1] == '1':
#                 return False
#             return True

#         @cache
#         def solve(row: int, col: int, p: str, curr: str) -> int:
#             if row >= m:
#                 return 0
#             if col == n:
#                 return solve(row + 1, 0, curr, '0' * n)
            
#             ans = 0
#             if seats[row][col] == '.' and check(col, p):
#                 new = curr[:col] + '1' + curr[col + 1:]
#                 ans = 1 + solve(row, col + 1, p, new)
            
#             new = curr[:col] + '0' + curr[col + 1:]
#             ans = max(ans, solve(row, col + 1, p, new))

#             return ans

#         return solve(0, 0, '0' * n, '0' * n)
class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        numRows, numCols = len(seats), len(seats[0])

        def check(col: int, prevMask: int) -> bool:
            if col <= 0:
                if prevMask & (1 << (col + 1)):
                    return False
            elif col >= numCols - 1:
                if prevMask & (1 << (col - 1)):
                    return False
            else:
                if prevMask & (1 << (col - 1)) or prevMask & (1 << (col + 1)):
                    return False
            return True

        @cache
        def solve(row: int, col: int, prevMask: int, mask: int) -> int:
            if row >= numRows:
                return 0
            if col == numCols:
                return solve(row + 1, 0, mask, 0)
            ans = 0
            if seats[row][col] == '.' and check(col, prevMask):
                if col == 0:
                    ans = 1 + solve(row, col + 1, prevMask, mask | (1 << (col)))
                elif not (mask & (1 << (col - 1))):
                    ans = 1 + solve(row, col + 1, prevMask, mask | (1 << (col)))
            ans = max(ans, solve(row, col + 1, prevMask, mask))
            return ans

        return solve(0, 0, 0, 0)
24900