<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:
        def preComputeSeats(n):
            h = {}
            for i in range(2**n):
                s=f'{i:0{n}b}'
                h[i]=[]
                for j in range(2**n):
                    t=f'{j:0{n}b}'
                    diff,superset = [],True
                    for k in range(n):
                        if s[k]==t[k]:
                            continue
                        elif s[k]=='1' and t[k]=='0':
                            superset = False
                            break
                        else: #s[k]==0 and t[k]==1:
                            diff.append(k)
                    if superset:
                        match = True
                        for k in range(1,len(diff)):
                            if diff[k]-diff[k-1] <= 1:
                                match = False
                                break
                        if match:
                            h[i].append((j,diff))
            return h


        m = len(seats)
        n = len(seats[0])
        h = preComputeSeats(n)

        #print(h)
        
        row = []
        for i in range(m):
            mask = 0
            for j in range(n):
                mask = mask<<1
                if seats[i][j]=='#':
                    mask += 1
            row.append(mask)
        
        row.append(2**n-1) # dummy row

        #print(row)
        
        dp = [[0 for _ in range(2**n)] for _ in range(m+1)]
        
        for i in range(m+1):
            for imask in range(2**n):
                if imask & row[i] == row[i]:
                #-- compute dp[i][imask]
                    maxV = 0
                    jmask = row[i-1]
                    for imaskx,diff in h[imask]:
                        jmaskx = jmask
                        for j in diff:
                            if j-1 >=0:
                                jmaskx = jmaskx | (1<<n-j)
                            if j+1 <= n-1:
                                jmaskx = jmaskx | (1<<n-j-2)
                        
                        if dp[i-1][jmaskx] + len(diff) > maxV:
                            maxV = dp[i-1][jmaskx] + len(diff)
                        
                        #print(f"  jmaskx={jmaskx:0{n}b} diff={diff} maxV={maxV}")

                    dp[i][imask] = maxV
                    #print(f"dp[{i}][{imask:0{n}b}]={dp[i][imask]} ")
            #print()
        return max(dp[m])

        '''
        for i in range(m):
            imask = row[i]
            jmask = row[i-1]
            for imaskx,diff in h[imask]:
                jmaskx = jmask
                for j in diff:
                    if j-1 >= 0:
                        jmaskx = jmaskx | ( 1<<(n-j-1) )
                    if j+1 <= n-1:
                        jmaskx = jmaskx | ( 1<<(n-j-1) )
                
                maxV = 0
                for kmask,_ in h[jmaskx]:
                    if dp[i-1][kmask] > maxV:
                        maxV = dp[i-1][kmask] 
                
                dp[i][imaskx] = maxV + len(diff)
            print(f"dp[{i}] = {dp[i]}")

        return max(dp[m-1])
        '''





        '''
        m = len(seats)
        n = len(seats[0])
        
        power = [0 for _ in range(m*n)]
        power[0]=1
        for i in range(1,m*n):            
            power[i] = power[i-1]*2

        mask = 0
        for i in range(m):
            for j in range(n):
                if seats[i][j] == "#":
                    p = i*n+j
                    mask = mask | power[p]

        
        if mask==2**(m*n)-1:
            return 0

        q = deque([(mask,0)])
        visited = {}
        count = -1
        while q: 
            count += 1           
            qlen = len(q)            
            #print(f"count = {count}")
            for _ in range(qlen):                            
                mask,taken = q.popleft()

                if mask in visited:
                    if taken <= visited[mask]:
                        continue
                visited[mask] = taken
                #print(f"taken={taken}")
                #print("  new qseats:")
                #for x in range(m*n):
                #    i,j = x//n,x%n
                
                for p in range(m*n): 
                    pmask =  power[p]
                    if mask & pmask==0: # can seat on the position p
                        
                        i,j = p//n, p%n
                        
                        #print(f"    put on seat({i,j}) takenx={takenx}")
                        maskx = pmask
                        for ix,jx in [(i,j-1),(i,j+1),(i-1,j-1),(i-1,j+1),(i+1,j-1),(i+1,j+1)]:
                            if 0<=ix<=m-1 and 0<=jx<=n-1:
                                px = ix*n + jx
                                maskx = maskx | power[px]                       

                        q.append((mask|maskx,taken+1))

        return count
        '''
228