<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])
        total = 1<<n
        dp = [[float('-inf') for _ in range(total)] for r in range(m)]

        def isOk1(arr,n):
            L = len(arr)
            flag = True
            for i in range(1,L):
                prev = arr[i-1]
                curr = arr[i]
                if(prev+1 == curr):
                    flag = False
                    break
                if(i+1<L):
                    nxt = arr[i+1]
                    if(curr + 1 == nxt):
                        flag = False
                        break
            return flag
        
        def isOk2(arr1,arr2):
            flag = True
            for v in arr2:
                if(v-1 in arr1):
                    flag = False
                    break
                if(v+1 in arr1):
                    flag = False
                    break
            
            return flag
        
        for r in range(m):
            for currMask in range(total):
                currFlag = True
                candidate = []
                for i in range(n):
                    if(currMask>>i&1 == 1):
                        if(seats[r][n-1-i] == '.'):
                            candidate.append(n-1-i)
                        else:
                            currFlag = False
                            break
                if(not currFlag):
                    continue
                
                candidate.sort()

                valid = isOk1(candidate,n)
                if(not valid):
                    continue
                if(r == 0):
                    dp[r][currMask] = len(candidate)
                    continue
                
                #current mask is valid
                #res without selecting prev row
                dp[r][currMask] = len(candidate)  
                for prevMask in range(total):
                    if(dp[r-1][prevMask] == float('-inf') or dp[r-1][prevMask] == 0):
                        continue

                    candidate2 = []
                    for i in range(n):
                        if(prevMask>>i&1 == 1):
                            candidate2.append(n-1-i)
                    candidate2.sort()
                    canSit = isOk2(candidate2,candidate)
                    if(canSit):
                        dp[r][currMask] = max(dp[r][currMask], dp[r-1][prevMask]+len(candidate))
                
        return max(dp[-1])                                                                                 
115