<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:
        # prev state
        self.m = len(seats)
        self.n = len(seats[0])

        def get_states(i, j, cur, states):
            if j == self.n:
                states.append(int(cur,2))
                return
            if seats[i][j] == '#':
                get_states(i,j+1,cur+'0', states)
            else:
                if ((j-1 >= 0 and cur[-1] == '1')):
                    get_states(i,j+1,cur+'0', states)
                else:
                    get_states(i,j+1,cur+'0', states)
                    get_states(i,j+1,cur+'1', states)

        def no_cheating(prev, cur):
            if self.n == 1:
                return True
            p = bin(prev)[2:].zfill(self.n)
            c = bin(cur)[2:].zfill(self.n)
            # print('p:',p,'c:',c)
            if c[0] == '1' and p[1] == '1':
                return False
            # print('self.n-1:', self.n-1, 'self.n-2:', self.n-2)
            if c[self.n-1] == '1' and p[self.n-2] == '1':
                return False
            for i in range(1, self.n-1):
                if c[i] == '1' and (p[i-1] == '1' or p[i+1] == '1'):
                    return False
            # print('no_cheating!')
            return True
        
        dp_1 = [0] * 256
        states = []
        get_states(0,0,'',states)
        for st in states:
            dp_1[st] = list(bin(st)).count('1')
            # print('st:', bin(st)[2:].zfill(self.n), 'n: ', dp_1[st])
        if self.n == 1:
            return max(dp_1)

        # for st in states:
        #     print(bin(st)[2:].zfill(self.n), end = " ")
        # print(" ")

        for i in range(1, self.m):
            dp_0 = copy.deepcopy(dp_1)
            prev_states = copy.deepcopy(states)
            dp_1 = [0] * 256
            states = []
            get_states(i,0,'',states)
            # print('line: ', i)
            # for st in states:
            #     print(bin(st)[2:].zfill(self.n), end = " ")
            # print(" ")
            for st in states:
                for p_st in prev_states:
                    if no_cheating(p_st, st):
                        dp_1[st] = max(dp_1[st], dp_0[p_st] + list(bin(st)).count('1'))
        # print('dp_1: ', dp_1)
        return max(dp_1)
96