<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:
        res=0
        m,n=len(seats), len(seats[0])
        initial= []
        b=[]
        for col in range(n):
            if seats[0][col]=='#':
                b.append(col)

        import collections
        from collections import defaultdict
        d=defaultdict(int)
        upper= int('1'*n , 2)
        base=[]
        for i in range(upper +1 ):
            binary_string= bin( i)[2:]
            need=n-len(binary_string)
            binary_string= '0'*need+ binary_string
            flag=True
            for j in range(1, n):
                if binary_string[j]==binary_string[j-1] and binary_string[j]=='1':
                    flag=False
                    break
            if flag:
                base.append(binary_string)


        dc=defaultdict(list)
        for i in range(len(base)):
            prev_row= base[i]
            for j in range(len(base)):
                cur_row= base[j]
                c_flag=True
                for k in range(1, n-1):
                    if cur_row[k]=='1' and prev_row[k-1]=='1':
                        c_flag=False
                        break
                    if cur_row[k]=='1' and prev_row[k+1]=='1':
                        c_flag=False
                        break
                if cur_row[0]=='1' and prev_row[1]=='1':
                    c_flag=False
                if cur_row[-1]=='1' and prev_row[-2]=='1':
                    c_flag=False
                if c_flag:
                    dc[cur_row ].append(prev_row)

        #print('dc ',dc)
        ##process the first row
        for binary_string in base:
            flag=True
            for col in b:
                if binary_string[col]=='1':
                    flag=False
                    break

            if flag:
                c=binary_string.count('1')
                d[binary_string]=c
                res=max(res, c)


        #print('d ',d)

        ###process the 2nd row and onward
        for row in range(1, m):
            b=[]
            temp_d= defaultdict(int)
            for col in range(n):
                if seats[row][col]=='#':
                    b.append(col)

            for binary_string in base:
                flag=True
                for col in b:
                    if binary_string[col]=='1':
                        flag=False
                        break
                if flag:
                    c= binary_string.count('1')



                    for cp in dc[binary_string]:
                        temp_d[binary_string]= max(temp_d[binary_string] , d[cp]+ c)

                        res=max(res,  d[cp]+ c)


            for key in temp_d:
                d[key]=temp_d[key]

            #print('row ,d ',row,d)
            #print('row temp_d ',row, temp_d)
            #print('*'*10)


        return res

64