<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 = len(seats)
        n = len(seats[0])
        def check(column, prev_mask):
            if column <= 0:
                if prev_mask & (1 << (column+1)):
                    return False
            elif column >= n-1:
                if prev_mask & (1 << (column-1)):
                    return False
            else:
                if prev_mask & (1 << (column-1)) or prev_mask & (1 << (column+1)):
                    return False
            return True
        @lru_cache(None)
        def place_students(row, column, prev_mask, mask):
            if row >= m:
                return 0
            if column >= n:
                return place_students(row+1, 0, mask, 0)
            put_student = 0
            skip_student = 0
            if seats[row][column] == '.' and check(column, prev_mask):
                if column == 0:
                    put_student = 1+place_students(row, column+1, prev_mask, mask | (1 << column))
                elif not (mask & (1 << (column-1))):
                    put_student = 1+place_students(row, column+1, prev_mask, mask | (1 << column))
            skip_student = place_students(row, column+1, prev_mask, mask)
            max_students = max(skip_student, put_student)
            return max_students
        return place_students(0, 0, 0, 0)


        # # correct but TLE
        # m = len(seats)
        # n = len(seats[0])
        # directions = [(0, 1), (0, -1), (-1, 1), (-1, -1)]
        # max_students = 0
        # def backtracking(seats, curr_row, curr_column, total_students):
        #     nonlocal max_students
        #     if curr_row == m:
        #         max_students = max(total_students, max_students)
        #         return
        #     if curr_column == n:
        #         backtracking(seats, curr_row+1, 0, total_students)
        #     else:
        #         backtracking(seats, curr_row, curr_column+1, total_students)
        #         cheating_seats = []
        #         for direction in directions:
        #             row = curr_row+direction[0]
        #             column = curr_column+direction[1]
        #             if 0 <= row < m and 0 <= column < n:
        #                 cheating_seats.append(seats[row][column])
        #         if seats[curr_row][curr_column] == '.' and -1 not in cheating_seats:
        #             seats[curr_row][curr_column] = -1
        #             backtracking(seats, curr_row, curr_column+1, total_students+1)
        #             seats[curr_row][curr_column] = '.'
        # backtracking(seats, 0, 0, 0)
        # return max_students

77