<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:
        BROKEN = '#'

        R = len(seats)
        C = len(seats[0])

        # path-dependent: whether we can put a student in seat at (r, c) depends on where we've put
        # other students.

        # DFS + backtracking can work here: for each seat
        #    > if it doesn't conflict: consider putting a student here and moving on
        #    > also consider NOT putting a student here

        # max 8 wide means 2^8, less in practice because we can't have adjacent seats occupied
        # this means we can cache - the number of people we can seat on rows r: only depends
        # on the seating pattern of the row above, which has fewer than 256 combinations.
        # Top-down DFS!

        R = len(seats)
        C = len(seats[0])

        def valid(above: int, curr: int) -> bool:
            """
            Returns true if curr is a valid seating arrangement given the row above,
            considering only the sight lines (i.e. doesn't check broken seats, etc.)
            """
            b = 1
            for c in range(C):
                if curr & b:
                    if curr & (b >> 1): return False
                    if above & (b >> 1): return False
                    if curr & (b << 1): return False
                    if above & (b << 1): return False

                b <<= 1

            return True

        @cache
        def count(above: int, r: int) -> int:
            """Returns the highest number of students that can be placed at r: given a pattern of students seated in the row above"""

            # current row: can't set adjacent bits, and can't set broken positions to 1
            # above row: no adjacent bits can be set
            # base case: above is 0

            if r == R: return 0

            mask = sum(1 << c for c in range(C) if seats[r][c] != BROKEN)
            enc = ((1 << C)-1) & mask # all occupied
            best = 0
            # TODO: is there a way to iterate through numbers that don't have adjacent bits set?
            while True:
                # check for adjacent seats in same row and prior row
                if valid(above, enc):
                    best = max(best, int.bit_count(enc) + count(enc, r+1))

                if enc == 0:
                    break
                else:
                    enc = (enc-1) & mask

            return best

        return count(0, 0)
127