<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:
        ans=0
        m=len(seats)
        n=len(seats[0])

        def getperms(row):
            ans=[]
            def dfs(ind,t):
                nonlocal ans
                if ind==n:
                    ans.append(t)
                    return 
                if row[ind]=="#":
                    dfs(ind+1,t+[row[ind]])
                else:
                    dfs(ind+1,t+[row[ind]])
                    dfs(ind+1,t+['#'])
            dfs(0,[])
            return ans

        def count(cur,prev):
            q=0
            for i in range(n):
                if cur[i]=='.':
                    c=0
                    if i-1>=0 and prev[i-1]=='.':
                        c+=1
                    if i+1<n and prev[i+1]=='.':
                        c+=1
                    if i-1>=0 and cur[i-1]=='.':
                        c+=1
                    if i+1<n and cur[i+1]=='.':
                        c+=1
                    if c==0:
                        q+=1
            return q
        def cmp():
            return {}
        dp=defaultdict(cmp)
        def main(a,row,prev):
            key=""
            for i in prev:
                key+=i
            if row==m:
                return 0
            if (row in dp) and (key in dp[row]):
                return dp[row][key]
            ans=0
            if row==0:
                perms=getperms(prev)
                for cur in perms:
                    q=0
                    for i in range(n):
                        if cur[i]=='.':
                            c=0
                            if i-1>=0 and cur[i-1]=='.':
                                c+=1
                            if i+1<n and cur[i+1]=='.':
                                c+=1
                            if c==0:
                                q+=1
                    ans=max(ans,q+main(a,row+1,cur))
            else:
                perms=getperms(a[row])
                for cur in perms:
                    q=count(cur,prev)
                    ans=max(ans,q+main(a,row+1,cur))
            dp[row][key]=ans
            return ans
        return main(seats,0,seats[0])
        
        

17900